거품 정렬

무작위 배열수의 거품 정렬 예

거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복합도가 $O(n^2)$로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

예제

오름차순으로 정렬하는 거품정렬의 과정은 다음과 같다.

55 07 78 12 42  첫 번째 패스
07 55 78 12 42
07 55 78 12 42
07 55 12 78 42
07 55 12 42 78  두 번째 패스
07 55 12 42 78
07 12 55 42 78
07 12 42 55 78  세 번째 패스
07 12 42 55 78
07 12 42 55 78  네 번째 패스
07 12 42 55 78  정렬 끝

의사 코드로 나타낸 알고리즘

procedure bubbleSort( A : list of sortable items ) defined as:
  for each i in 1 to length(A) do:
       for each j in length(A) downto i + 1 do:
         if A[ j ] < A[ j - 1 ] then
           swap( A[ j ],  A[ j - 1 ] )
         end if
       end for
  end for
end procedure

바깥 고리

• Bubblesort code