[정렬] 버블 정렬과 삽입 정렬
버블 정렬
- 정의 : 버블 정렬은 말 그대로 거품 정렬이다. 리스트 안의 원소들이 점점 뒤로 밀려들어가기 때문에 이 모습이 마치 거품이 수면위로 올라오는 듯한 모습처럼 보여 지어진 이름이다.
- 방법 : 맨 왼쪽 원소부터 바로 이웃한 원소와 비교해 가면서, 큰 수가(내림차순인 경우 작은 수가) 오른쪽으로 가도록 교환한다. 이 때 맨 끝과 그 앞의 원소까지 비교하면, 가장 큰 원소(또는 가장 작은 원소)를 찾은 것이므로, 다시 나머지 n-1개 수에 대하여 다시 반복한다.
- 예시
9 5 2 4 1 라는 배열이 있다고 가정하자. 오름차순을 만드는 버블 정렬을 순차적으로 표현하면
9 5 2 4 1 -> 5 9 2 4 1 -> 5 2 9 4 1 -> 5 2 4 9 1 -> 5 2 4 1 9
5 2 4 1 9 -> 2 5 4 1 9 -> 2 4 5 1 9 -> 2 4 1 5 9
2 4 1 5 9 -> 2 4 1 5 9 -> 2 1 4 5 9
2 1 4 5 9 -> 1 2 4 5 9
이렇게 주어진 배열을 오름차순으로 정렬할 수 있다.
- C++ 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
#include <stdio.h>
int main() {
int mat[5] = {9,5,2,4,1};
//bubble sort
for (int i = 0; i < 5; i++) {
for (int j = i; j < 5; j++) {
if (mat[i] > mat[j]) { //두 수 swap
int temp = mat[i];
mat[i] = mat[j];
mat[j] = temp;
}
}
}
for (int i = 0; i < 5; i++) {
printf("%d ", mat[i]);
}
return 0;
}
|
cs |
이런 식으로 for 문을 두 번 돌면서 두 수를 계속 비교해 왼쪽에 있는 수가 더 크면 오른쪽 수와 교환한다.
-
시간 복잡도
처음 가장 큰 원소를 구할 때 n-1 비교, 두번째 큰 원소를 구할 때 n-2번 비교 , ...(n-1) + (n-2) + ... + 1 = n(n-1)/2 = O(n^2)
이처럼 입력과 무관하게, n개의 값을 정렬할 때 항상 똑같은 횟수의 비교를 수행한다 (그 전에 정렬이 완료되었어도 컴퓨터가 알아서 멈추지 않고 계속 비교한다!)
,
삽입 정렬
- 정의 : 정렬 대상이 될 원소들을 두 부분으로 나눈 후 순차적으로 오른쪽 원소들을 왼쪽으로 삽입시켜 정렬한다.
- 방법 : 원소들을 담고 있는 배열을 "아직 정렬되지 않은 부분", "정렬된 부분"으로 각각 나눈 후, 정렬되지 않은 부분에서 원소들을 하나 씩 꺼내 정렬된 부분에 삽입한다. 이 때 삽입은 "정렬된 부분" 의 가장 큰 원소(오른쪽)부터 왼쪽으로 비교해나가면서 진행한다.
- 예시 : {5,3,1,4,2} 배열이 있다고 가정하자. 배열의 가장 왼쪽 부분 즉 {5} 왼쪽부분({})을 "정렬된 부분"이라하고(아직 아무것도 안들어있다), 오른쪽 부분({5,3,1,4,2})을 "정렬되지 않은 부분"이라고 두자. 이후 정렬되지 않은 부분의 첫번째 원소부터 오른쪽으로 집어넣어보자
| 순서 | 정렬된부분(왼쪽) | 정렬되지 않은부분(오른쪽) |
| 1 | 비어있음 | 5 3 1 4 2 |
| 2 | 5 | 3 1 4 2 |
| 3 | 5 3 -> 3 5 | 1 4 2 |
| 4 | 3 5 1 -> 3 1 5 -> 1 3 5 | 4 2 |
| 5 | 1 3 5 4 -> 1 3 4 5 | 2 |
| 6 | 1 3 4 5 2 ->> 1 2 3 4 5 | 비어있음 |
위 표의 밑줄은 이 부분에서 비교를 진행한다는 의미이다.
이런식으로 하나의 배열 안에서 정렬을 할 수 있고, 위의 버블 정렬과 다르게 적절한 위치를 찾으면 거기서 멈출 수 있다.
- C++ 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#include <iostream>
using namespace std;
//삽입 정렬
void insertionSort(int arr[], int n) { //배열과 배열 원소의 개수를 받는다
int temp = 0; //비교할 값을 저장할 변수
for (int i = 1; i < n; i++) { //가장 왼쪽 값은 옮겨둔것으로 설정한 후 나머지 n-1개의 원소만 옮김
temp = arr[i];
int sort_cnt = i - 1; //저장 공간 변수 index
while (sort_cnt >= 0 && arr[sort_cnt] > temp) { //배열범위 0 이상 and 정렬된 부분의 원소가 꺼낸 값보다 클 때
arr[sort_cnt + 1] = arr[sort_cnt];
sort_cnt--;
}
arr[sort_cnt + 1] = temp;
}
}
int main()
{
int arr[5] = { 5,3,1,4,2 }; // 주어진 배열
int n = 5; // 원소의 개수
insertionSort(arr, n);
for (int i = 0; i < n; i++) {
printf("%d ",arr[i]);
}
return 0;
}
|
cs |
- 시간복잡도 : 삽입정렬은 위에서도 말했듯이 숫자 입장에서 자기가 적절한 위치에 왔다~ 싶으면 멈춘다(왼쪽값보다 자기가 크면 반복을 멈추고 다음 수로 넘어간다)
- 최적 : 이미 배열이 정렬된 경우 숫자를 그냥 옮기고 딱 한번만 비교하면 더이상 비교를 하지 않아서 시간복잡도는 O(n)이 된다.
- 최악 : 배열이 내림차순으로 정렬된 경우 최적의 경우 + 값을 옮길때마다 왼쪽에있는 정렬된값들을 전부다 비교해야하므로 1 + 2 + ... + (n-1) = n(n-1)/2 = O(n^2) 번 비교한다.
위에서 살펴본 두 정렬은 모두 시간복잡도가 O(n^2)이다.
그렇다면 정렬은 O(n^2)이 최적일까?? 당연히 아니다
하지만, 인접한 두 원소를 교환하는 방식으로는 O(n^2)가 최적이다.
왜냐하면 n개의 원소들 중 둘을 뽑는 방법은 (n,2)가지가 있는데, 최악으로 정렬된 경우 이 방법 전부다 사용하여야하기때문에 (n,2) = O(n^2) 번 교환이 필요하다.
그렇다면 인접한 두 원소를 비교하여 정렬하는 방법 말고 다른 방법이 있을까?? 그렇다!
간단히 생각해보자면 크게 크게 정렬을 하면서 나누면 된다. 이를 분할 정복 기법이라고 하는데
다음 장에서 살펴보겠다.