이번에는 버블정렬에 대해서 알아보도록 하죠!
버블정렬은 바로 옆에있는값과 비교를 해 만약 더욱 작은값이 있다면 그 숫자를 앞으로 보내는것입니다. 결과는 직관적으로 가장 큰 값이 맨 뒤로 보내지게 됩니다. 굉장히 쉽지만 굉장히 비효율적입니다.. ㅎㅎ 선택정렬보다 더 비효율적이라고 할 수 있습니다. 그래도 한번 해봅시다!
전과 같은 예제를 가지고 와 볼게요 1/7/3/5/8/6/9/2/4에 대해 정렬을 하는 예제입니다!
#include <iostream> using namespace std; int main() { int temp; int array[9] = { 1, 7, 3, 5, 8, 6, 9, 2, 4 }; for (int i = 0; i < 9; i++) { for (int j = 0; j < 8 - i; j++) { if (array[j] > array[j+1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1] = temp; } } } for (int i = 0; i < 9; i++) { cout << array[i] << " "; } return 0; }
💡 이제 코드를 하나하나 뜯어 봅시다!
j for문이 왜 'j < 8-i'의 형태인지 생각해봅시다!
1/7/3/5/8/6/9/2/4(횟수 x) -> 1/7/3/5/8/6/9/2/4 -> 1/3/7/5/8/6/9/2/4 -> 1/3/5/7/8/6/9/2/4 -> 1/3/5/7/8/6/9/2/4 -> 1/3/5/7/6/8/9/2/4 -> 1/3/5/7/6/8/9/2/4 -> 1/3/5/7/6/8/2/9/4 -> 1/3/5/7/6/8/2/4/9
이렇게 8번의 반복비교가 이루어 지고 나면 9가 맨 오른쪽이로 이동해 있게됩니다. 9가 맨 오른쪽으로 이동된 이후에는 8번을 반복할 필요가 없고 7번만 수행하면 되기때문에 8-i번의 반복을 통해 자리를 바꾸고 비교를 할 수 있게됩니다!
첫 번째 패스에서 8번의 비교와 7번의 교환이 발생합니다.
두 번째 패스에서 7번의 비교와 6번의 교환이 발생합니다.
세 번째 패스에서 6번의 비교와 5번의 교환이 발생합니다.
네 번째 패스에서 5번의 비교와 4번의 교환이 발생합니다.
다섯 번째 패스에서 4번의 비교와 3번의 교환이 발생합니다.
여섯 번째 패스에서 3번의 비교와 2번의 교환이 발생합니다.
일곱 번째 패스에서 2번의 비교와 1번의 교환이 발생합니다.
여덟 번째 패스에서 1번의 비교와 0번의 교환이 발생합니다.
버블 정렬의 시간복잡도 또한 O(N^2)이지만, 컴퓨터가 내부적으로 위치를 계속적으로 옮겨줘야 하므로 선택정렬보다 더 많은 시간이 소요된다 할 수 있습니다!
