Bubble sort

※ 이해가 잘 되지 않는 부분은 위키피디아 원문을 함께 실었습니다.

버블 정렬은 인접한 항목의 각 쌍을 비교하여, 자리를 작업를 반복적으로 수행하는 간단한 정렬 알고리즘입니다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다. 원소의 비교만으로 동작하기 때문에 비교 정렬입니다. 알고리즘은 간단하지만, 크기가 큰 목록을 정렬할 때는 적합하지 않습니다.

성능
원소의 갯수가 n개 일 때, 최악의 경우와 평균 복잡도는 O(n²) 입니다. 최악의 경우나 평균 복잡도가 O(nlogn)인 많은 정렬 알고리즘이 존재합니다. 심지어, 삽입 정렬 같은 복잡도가 O(n²)인 다른 정렬 알고리즘도, 버블 정렬보다 더 나은 성능을 보이는 경향이 있습니다. 따라서, n값이 클 때 버블 정렬은 실용적이지 못한 정렬 알고리즘 입니다.

토끼와 거북이
The positions of the elements in bubble sort will play a large part in determining its performance. Large elements at the beginning of the list do not pose a problem, as they are quickly swapped. Small elements towards the end, however, move to the beginning extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.

Various efforts have been made to eliminate turtles to improve upon the speed of bubble sort. Cocktail sort is a bi-directional bubble sort that goes from beginning to end, and then reverses itself, going end to beginning. It can move turtles fairly well, but it retains O(n²) worst-case complexity. Comb sort compares elements separated by large gaps, and can move turtles extremely quickly before proceeding to smaller and smaller gaps to smooth out the list. Its average speed is comparable to faster algorithms like quicksort.

버블 정렬에서 원소의 위치는 성능을 결정하는데 큰 역할을 합니다. 목록의 시작점에 큰 원소는 빠르게 순서가 바뀌는 것에 문제가 되지 않습니다. 그러나 끝에 있는 작은 원소는 매우 천천히 처음으로 이동합니다. 이런 형태의 원소에 토끼와 거북이라는 이름이 붙여졌습니다.
버블 정렬의 속도 향상을 위해 거북이를 제거 하기 위한 다양한 시도가 있습니다. 칵테일 정렬은 이런 목표를 꽤 달성 했지만, 최악의 경우 O(n²)의 복잡도를 갖고 있습니다. 빗 정렬은 큰 gap으로 분리된 원소를 비교함으로써, 거북이를 매우 빠르게 이동시킬 수 있습니다. 더 작고 작은 gap으로 부드럽게 진행함으로써, 이 알고리즘의 평균 속도는 더 빠른 알고리즘인 퀵 정렬과 비교할 만 합니다.

Step-by-step example
숫자 배열 "5 1 4 2 8"을 버블 정렬 알고리즘을 사용하여, 가장 작은 숫자부터 가장 큰 숫자 순으로 정렬하는 예제입니다. 각 pass 에서 비교 되어지는 원소는 굵게 적었습니다. 3번의 pass가 필요합니다.

First Pass:
( 5 1 4 2 8 ) → ( 1 5 4 2 8 ), 처음 두 개의 원소를 비교하여 순서를 바꿉니다.
( 1 5 4 2 8 ) → ( 1 4 5 2 8 ), 5 > 4 이므로 순서를 바꿉니다.
( 1 4 5 2 8 ) → ( 1 4 2 5 8 ), 5 > 2 이므로 순서를 바꿉니다.
( 1 4 2 5 8 ) → ( 1 4 2 5 8 ), 8 > 5 정렬되어 있으므로 순서를 바꾸지 않습니다.

Second Pass:
( 1 4 2 5 8 ) → ( 1 4 2 5 8 )
( 1 4 2 5 8 ) → ( 1 2 4 5 8 ), 4 > 2 이므로 순서를 바꿉니다.
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
정렬은 완료되었지만, 알고리즘은 완료 여부를 알 수 없습니다.
순서가 변하지 않는 한 번의 전체 pass를 수행합니다.

Third Pass:
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )
( 1 2 4 5 8 ) → ( 1 2 4 5 8 )

구현

---

Pseudocode implementation (의사코드)

알고리즘은 다음과 같이 표현될 수 있습니다. (0-based array):

procedure bubbleSort( A : list of sortable items )
   repeat     
     swapped = false
     for i = 1 to length(A) - 1 inclusive do:
       /* if this pair is out of order */
       if A[i-1] > A[i] then
         /* swap them and remember something changed */
         swap( A[i-1], A[i] )
         swapped = true
       end if
     end for
   until not swapped
end procedure

Optimizing bubble sort (최적화)

The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time:

버블 정렬은 n번째 pass에서 n번째 큰 요소를 찾아 최종 위치로 이동하는 것을 관찰함으로써 쉽게 최적화 할 수 있습니다. 그러면 내부 루프는 n번 째 실행시 마지막 n-1 번째 원소의 검토를 하지 않아도 됩니다.

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       swapped = false
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             swapped = true
          end if
       end for
       n = n - 1
    until not swapped
end procedure

보다 일반적으로, 하나 이상의 원소가 단일 pass에서 그들의 최종 위치로 이동할 수 있습니다. 특히 모든 원소의 정렬이 완료된 후에는 다시 검사할 필요가 없습니다. 이것은 많은 원소의 비교를 건너 뛸 수 있고, 결과적으로 최악의 경우 비교 횟수에서 50% 성능이 개선됩니다. (자리 바꿈의 횟수는 그대로입니다.), 새로운 코드는 "swapped" 변수를 포함하여, 복잡도를 개선했습니다.
의사 코드는 다음과 같습니다:

procedure bubbleSort( A : list of sortable items )
    n = length(A)
    repeat
       newn = 0
       for i = 1 to n-1 inclusive do
          if A[i-1] > A[i] then
             swap(A[i-1], A[i])
             newn = i
          end if
       end for
       n = newn
    until n = 0
end procedure 

버블 정렬 처럼 인접한 원소를 반복적으로 비교하고, 자리를 바꾸면서 성능을 개선한 대체 알고리즘으로 cocktail shaker sort 등이 있습니다.

출처 : http://en.wikipedia.org/wiki/Bubble_sort 발췌 번역(/w Google 번역)