거품 정렬(Bubble sort)

• 2018-04-07
• 초안 작성

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  정렬 끝

• 의사 코드