거품 정렬

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

거품 정렬(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

소스 코드

Java

public static void main(String[] args) {
        int[] array = {12, 123,123, 6,23,53,52,23,5,12,7452,123};
        int temp;
 
        for(int i = 0; i < array.length; i++){
                for(int j = i + 1; j < array.length; j++){
                        if(array[i] > array[j]){
                                temp = array[i];
                                array[i] = array[j];
                                array[j] = temp;
                        }
                }
        }
 
        for(int i = 0; i < array.length; i++)
                System.out.print(array[i] + " ");
}

바깥 고리

• Bubblesort code