개요
이번 글에서는 이전의 선택 정렬과 유사한 또 하나의 기초적이고 간단한 정렬 방법인 버블 정렬을 소개하고자 한다. 또한, 선택 정렬과 비교하며 알고리즘의 효율성에서 어떤 차이를 가지는지 알아보고자 한다.
버블 정렬
"3 1 2 9 8 4 7 10 5 6
위 숫자들을 오름차순으로 정렬하라."
버블 정렬은 연속된 두 수의 비교를 통해 작은 수를 왼쪽으로 위치시켜 순서대로 나열하는 방법이다. 이를 수행하게 되면 가장 큰 수부터 순서대로 마지막 인덱스에 위치하게 된다.
수행 과정
버블 정렬의 수행 과정은 다음과 같다.
1. [3, 1, 2, 9, 8, 4, 7, 10 ,5, 6]에서 index 0과 1을 비교하여 작은 값을 찾아낸다.
2. '3'과 '1' 중 '1'이 더 작은 수이므로 두 수의 위치를 갱신한다. 이때 내부 for문의 반복 횟수는 9번이다.
-> [1, 3, 2, 9, 8, 4, 7, 10 ,5, 6]
3. 이 과정을 반복하여 모든 인덱스의 비교가 끝나면 가장 큰 수가 가장 우측에 위치하게 되어 다음 반복에서 제외할 수 있게 된다. 따라서, '10'을 제외한 [1, 2, 3, 8, 4, 7, 9, 5, 6]에서 1~2번 과정을 다시 반복한다. 이때 내부 for문의 반복 횟수는 8번이다.
4. 1~3번 과정을 모두 재배치할 때까지 반복한다. 이때 외부 for문의 반복 횟수는 10번이다.
시간 복잡도
위 과정을 모두 반복했을 때의 시간 복잡도는 선택 정렬과 동일하게 O(N^2)이 된다. 하지만 전체 배열에서 가장 작은 수를 찾은 다음 배열을 한번 갱신하는 선택 정렬과 달리 버블 정렬은 모든 반복에서 배열을 갱신하게 된다. 그렇기에 버블 정렬은 선택 정렬과 동일한 시간 복잡도를 가졌지만 더욱 비효율적인 알고리즘이다.
코드 구현
버블 정렬을 코드로 구현하면 다음과 같다.
#include <iostream>
int array[10] = {3, 1, 2, 9, 8, 4, 7, 10, 5, 6};
int main()
{
int temp;
for (int i=0; i < 10; i++){
for (int j=0; j < 9 - i; j++){
if (array[j] > array[j+1]){
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
std::cout << "array : ";
for (int i=0; i < 10; i++){
std::cout << array[i] << ' ';
}
return 0;
}
//array : 1 2 3 4 5 6 7 8 9 10Reference
