이번 시간에는 버블 정렬에 대해 알아보도록 하겠다.
버블 정렬은 가까이에 있는 두 숫자끼리 비교를 해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것이다.
정렬 알고리즘 중 가장 쉽지만 가장 비효율적인 정렬 방법이다.
앞서 배웠던 선택 정렬과 다르게 뒤에서부터 정렬이 된다.
코드로 구현해보면
#include <stdio.h>
int main() {
int i, j, temp;
int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
for (i = 0; i < 10; i++) {
for (j = 0; j < (10 - i) - 1; j++) {
if (array[j] > array[j + 1]) {
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
for (i = 0; i < 10; i++) {
printf("#%d %d\n", i, array[i]);
}
return 0;
}
이 된다.
출력 결과는
#0 1
#1 2
#2 3
#3 4
#4 5
#5 6
#6 7
#7 8
#8 9
#9 10
로, 역시나 잘 정렬된 것을 볼 수 있다.
버블 정렬은 선택 정렬과 마찬가지로 O(n^2)의 시간 복잡도를 가져서 비효율적이다.
역시나 선택 정렬처럼 위의 예는 첫번째는 10개를 모두 살펴보고, 두번째에는 맨 앞에 있는 1을 제외한 나머지 9개, 이런 식으로 계속 진행하다보면 10 + 9 + 8 + ... 이렇게 되어 n(n+1)/2를 만족하기 때문에 O(n^2)이다.
단지 선택 정렬과 다른 것은 버블 정렬은 맨 오른쪽, 맨 마지막의 가장 큰 원소부터 정렬된다는 점이다.
하지만 실제로 작동해보면 버블 정렬이 선택 정렬보다 더 느리게 동작하는데, 그 이유는 버블 정렬의 경우에는 당장 옆의 원소와 비교해서 자리를 바꾸는 연산을 수행하고,
temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
이렇게 총 3개의 명령어를 수행한다.
하지만 선택 정렬의 경우에는 가장 작은 것을 임시 변수에 저장한 다음, 맨 마지막에 이번 차례 원소와 가장 작은 원소와 단 한 번만 swapping하는 연산을 하므로, 버블 정렬의 연산량이 더 많다.
다음 시간에는 삽입 정렬에 대해 알아보도록 하겠다.
'C++ Programming > 알고리즘 정리' 카테고리의 다른 글
[C++] 큐(Queue) (0) | 2020.05.07 |
---|---|
[C++] 스택(Stack) (0) | 2020.05.07 |
[C++] 퀵 정렬 (Quick Sort) (0) | 2020.05.06 |
[C++] 삽입 정렬(Insertion Sort) (0) | 2020.05.06 |
[C++] 선택 정렬 (Selection Sort) (0) | 2020.05.06 |