버블정렬 Bubble Sorting

버블정렬

버블정렬도 선택정렬처럼 제일 큰 원소를 끝자리로 옮기는 작업을 반복하는 정렬이다.

다만, 제일 큰 원소를 오른쪽으로 옮기는 방법이 다를 뿐이다.

bubbleSort(A[], n) {

for last (last의 값은 n에서부터 2까지) {

for i (i의 값은 1에서 last까지) {

if (A[i] > A[i+1]) then A[i] 와 A[i+1]의 값을 교환 (원소 교환)

}

}

}

위의 코드는 버블정렬의 수도 코드(sudo code)이다.

버블 정렬의 알고리즘은 크게 두 개의 for 루프로 이루어져 있다. 첫 번째 루프는 선택정렬의 for 루프와 역할이 똑같다. 루프를 돌 때마다 제일 큰 원소를 맨 오른쪽으로 보내고 정렬할 배열의 크기를 하나씩 줄인다. 안쪽의 for 루프가 하는 일은 가장 큰 원소를 맨 오른쪽으로 보내는 것이다. 이 부분이 선택정렬과 다르다. 선택정렬이 가장 큰 수를 찾은 다음 가장 오른쪽 수와 바꾸는 반면, 버블 정렬은 왼쪽부터 이웃한 수를 비교하면서 순서가 제대로 되어 있지 않으면 하나하나 바꾸어 나간다.

버블정렬의 시간 복잡도는 O(n^2)으로 선택정렬과 같다. 퀵정렬이나 병합정렬등 더욱 효율적인 정렬들이 많음에도 버블정렬이 사용되는 이유는 그 코드를 작성하기가 간편하기 때문이다.

아래의 이미지는 위키피디아에 올라와 있는 버블 정렬의 코드들이다.

1) sudo code

2) C 언어로 작성한 버블정렬

3) C++로 작성한 버블정렬