거품 정렬

위키백과 ― 우리 모두의 백과사전.

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

목차 1 예제 2 의사 코드로 나타낸 알고리즘 3 바깥 고리

[편집] 예제

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

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

이 글은 전산학에 관한 토막글입니다. 서로의 지식을 모아 알차게 문서를 완성해 갑시다.

v • d • e 정렬 알고리즘
이론	계산 복잡도 이론 | 점근 표기법 | 완전순서 | 비교 정렬
교환 정렬	거품 정렬 | 칵테일 정렬 | 홀짝 정렬 | 콤 정렬 | 난쟁이 정렬 | 퀵 정렬
선택 정렬	선택 정렬 | 힙 정렬
삽입 정렬	삽입 정렬 | 셸 정렬 | 트리 정렬 | 라이브러리 정렬
합병 정렬	합병 정렬 | 스트랜드 정렬
비(非)비교 정렬	기수 정렬 | 버킷 정렬 | 계수 정렬 | 비둘기집 정렬 | 버스트 정렬