버블정렬 (Bubble Sort)

버블정렬은 문자 그대로 마치 공기방울이 수면 위로 떠오르듯 가장 큰 레코드가 한 칸씩 한 칸씩 오른쪽으로 떠올라오는 정렬입니다.

버블정렬 순서
ㅇ 다음과 같은 숫자의 나열이 있을 경우 버블 정렬을 해보자.

1. 첫번째 칸의 22와 그 다음칸에 있는 37을 비교 합니다. 만약 22가 더 크다면 두 수를 스왑(Swap)하고, 아니라면 다음칸으로 이동합니다.

2. 두번째 칸의 37과 그 다음칸에 있는 15를 비교 합니다. 만약 37이 더 크다면 두 수를 스왑(Swap)하고, 아니라면 다음칸으로 이동합니다.

3. 세번째 칸의 37과 그 다음칸에 있는 19를 비교 합니다. 만약 37이 더 크다면 두 수를 스왑(Swap)하고, 아니라면 다음칸으로 이동합니다.

4. 네번째 칸의 37과 그 다음칸에 있는 12를 비교 합니다. 만약 37이 더 크다면 두 수를 스왑(Swap)하고, 아니라면 다음칸으로 이동합니다.

5. 네번째와 다섯번째 칸이 마지막으로 비교 할 수 있었던 칸이 였기 때문에 마지막까지 오른쪽으로 떠오른 37에 대해서 위치를 확정합니다.

위의 동작을 하게 되면 숫자 하나에 대해서 정렬을 수행한 것입니다. 만약  5개의 숫자 나열이라면 위와 같은 수행을 4번 해야되고, 10개의 숫자 나열이라면 9번을 해야 합니다. 즉, N개의 숫자 나열은 N-1번 수행해야 합니다.

두번째 동작을 글로 적어보자면, 다시 첫번째 숫자인 22와 그 다음칸인 15를 비교하면 22가 크기 때문에 스왑합니다. 그리고 두번째인 22와 세번째인 19를 비교하면 22가 크기 때문에 스왑합니다. 그리고 다시 세번째인 22와 네번째인 12를 비교하면 22가 크기 때문에 스왑합니다. 정렬되지 않는 숫자의 나열은 네번째칸이 정렬되지 않는 숫자의 나열 중 가장 끝부부이기 때문에 두번째 정렬을 마칩니다.
그리고 세번째 동작, 네번째 동작을 하게 되면 위의 5개의 숫자 나열은 오름차순으로 정렬되게 됩니다.

 Tip
버블정렬은 스왑(Swap)이 잦으므로 큰 레코드에 대해서 선택 정렬보다 좋지 않습니다. 그러나 이미 정렬되어 있는 데이터를 정렬 할 경우 알고리즘 효율은 O(N)의 효율을 보입니다.