Bubble Sort

버블정렬알고리듬

버블 정렬은 가장 기본적인 정렬 알고리듬이다. 물속에서 거품이 떠오르는 것처럼 큰 값이 뒤쪽으로 떠올라가는 과정을 계속 반복하는 방식이다. 예를 들어 다음과 같은 정수값의 배열이 있다고 가정해보자.

[45][53][26][93][62][20][33][17]

버블 정렬을 사용해서 이 배열을 오름차순으로 정렬해볼 것이다. 버블 정렬의 알고리듬은 매우 간단하다.

  1. 배열의 두 번째 원소에서부터 시작한다.
  2. 현재위치의 원소와 바로 앞 위치의 원소를 비교, 현재 위치의 원소가 더 작으면 앞의 원소와 자리를 바꾼다.
  3. 다음 위치로 이동한다.
  4. 2~3의 과정을 배열의 마지막까지 이를 때까지 반복한다.
  5. 다시 1~4의 과정을 반복한다. 이 과정에서 자리 바꿈이 한 번도 일어나지 않았다면 정렬된 상태로 판단한다.

그럼 이 알고리듬을 따라 가보자.

[45][53][26][93][62][20][33][17]

우선 배열의 두 번째, 첫번째 원소를 비교한다.

[45][53][26][93][62][20][33][17]
~~~~~~~~
</code></pre>

뒤쪽의 값이 크므로 패스.

<pre><code>[45][53][26][93][62][20][33][17]
    ~~~~~~~~~

다음 위치에서 검사. 뒤쪽의 값이 작다. 자리를 교환한다.

[45][26][53][93][62][20][33][17]
    ~~~~~~~~

교환된 상태. 그리고 다음 위치로 이동

[45][26][53][93][62][20][33][17]
        ~~~~~~~~

93이 더 크다. 패스하고 다음 위치로 이동

[45][26][53][93][62][20][33][17]
            ~~~~~~~~

62가 더 작다. 위치 이동. 사실 93은 배열 내에서 가장 큰 값이므로 계속해서 자리 바꿈이 일어날 것이다.

[45][26][53][62][93][20][33][17]
            ~~~~~~~~

이동.

[45][26][53][62][93][20][33][17]
                ~~~~~~~~

역시 작다.

[45][26][53][62][20][93][33][17]
                ~~~~~~~~

자리 바꾸고,

[45][26][53][62][20][93][33][17]
                    ~~~~~~~~

이동,

[45][26][53][62][20][33][93][17]
                    ~~~~~~~~      

자리 바꿈.

[45][26][53][62][20][33][93][17]
                        ~~~~~~~~ 

이동

[45][26][53][62][20][33][17][93]
                        ~~~~~~~~  

자리바꿈. 이렇게 한 번의 싸이클이 끝났다. 한 싸이클이 끝날 때 마다 가장 큰 값이 뒤로 밀려나게 된다. 자 이제 다음 사이클을 돌려보면

[26][45][53][20][33][17][63][93]
                        ~~~~

두 번째로 큰 63이 제 위치를 찾아가게 된다. 그리고 이어지는 사이클들을 돌려보면…

[26][45][20][33][17][53][63][93]
[26][20][33][17][45][53][63][93]
[20][26][17][33][45][53][63][93]
[20][17][26][33][45][53][63][93]
[17][20][26][33][45][53][63][93]                            

위와 같은 과정을 겨쳐서 정렬이 완료된다. 버블 정렬은 구현이 간단한 대신, 효율이 좀 떨어지는 단점이 있다.

def bubbleSort(alist):
    changed = True
    while changed:
        changed = False
        for i in range(1, len(alist)):
            if alist[i - 1] > alist[i]:
                alist[i-1], alist[i] = alist[i], alist[i-1]
                changed = True