개요
인접하는 두 항을 비교해서 뒷 항이 앞 항보다 작으면 두 항을 교환하는 과정을 반복한다. 쉽게 생각하면, 우선 제일 큰거 맨 위로 올리고, 그다음 큰거 맨 위로 올리를 모든 항이 정렬될 때까지 반복하는 것이다.
예제
오름차순으로 정렬하는 거품정렬의 과정은 다음과 같다.
55 07 78 12 42 초기값[파란색은 sorting] 07 55 78 12 42 첫 번째 패스(pass) 07 55 78 12 42 07 55 12 78 42 07 55 12 42 78 두 번째 패스(pass) 07 55 12 42 78 07 12 55 42 78 07 12 42 55 78 세 번째 패스(pass) 07 12 42 55 78 네 번째 패스(pass) 07 12 42 55 78 다섯 번째 패스(pass) 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