All that Sort - [1] Bubble Sort (거품정렬)

찾기(search) 와 정렬(sort)는 뗄래야 뗄 수 없는 존재로 현대 컴퓨팅의 매우 중요한 분야이다.
조금이라도 프로그래밍을 해보았다면, 효율적인 정렬과 찾기 방법이야말로 프로그램 최적화의 첫 단계라는 것을 알 것이다.
그래서 알고리즘 수업 시간에 배웠던 정렬 알고리즘들에 대해 하나씩 점검/정리 해보고자 한다.

[1] Bubble Sort (거품정렬)

다들 수영장에서 수영을 해 본 기억이 있을 것이다. 수영하기, 물먹기-_- 등등 다양한 액션이 나오는 가운데 혹 물 속에서 숨을 뱉어보았는가? 자신의 입에서 나온 기체 방울이 점점 커지면서 수면으로 상승하는 것을 보았을 것이다. 이와 동일한 방법이 Bubble Sort 이다. 말 그대로, 거품정렬. 일단 예시를 보자.

4

9

3

6

2

버블 소트는 처음부터 끝까지 모든 가지 수를 비교하는 정렬이다. 맨 처음엔 가장 첫 원소와 두 번째 원소를 비교한다. 그리고 앞의 원소가 뒤의 원소보다 크면 두 수의 자리를 바꾼다. 처음 비교에서 4와 9는 4<9 이므로 다음 비교로 넘어간다.

두 번째 비교에선  9 와 3을 비교하는데, 9>3 이므로 두 수의 자리를 바꾼다.

4

3

9

6

2

같은 방법으로 끝까지 비교하면 다음과 같이 1회의 실행이 완료.

4

3

6

2

9

이와 같이 한 회의 실행이 끝났을 때 얻어지는 것은? 9에 주목해보자. 가장 큰 수가 제 자리를 찾아갔다는 것이다!
이런 식으로 끝에서 첫 번째, 두 번째... 끝에서 마지막 번째 수까지 다 비교해 자리를 찾아주면 정렬 끝.

이제 psuedo code 를 보자.(wiki 참조)

procedure bubbleSort( A : list of sortable items ) defined as:
  n := length( A )
  do
    swapped := false
    for each i in 0 to n - 1  inclusive do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
    n := n - 1
  while swapped
end procedure

여기서 swapped 는 첫 번째 실행 동안 아무 교환이 일어나지 않았을 경우 이미 정렬이 된 리스트라는 뜻이므로 코드를 종료하기 위함이다. 이러한 형태를 bubble sort early termination version 이라고도 한다.

Time Complexity 는 O(n²)  인데, 비교의 횟수가 (n-1) + (n-2) + ... + 1 = {(n-1)(n-2)}/2 이기 때문이다.