CS -알고리즘 버블 정렬

정렬되지 않은 리스트를 탐색하는 것 보다 정렬한 뒤 탐색하는 것이 더 효율적입니다.

정렬 알고리즘 중 하나는 버블 정렬입니다.

버블 정렬은 두 개의 인접한 자료 값을 비교하면서 위치를 교환하는 방식으로 정렬하는 방법을 말합니다.

버블 정렬은 단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중합니다.

이 접근법은 간단하지만 단 하나의 요소를 정렬하기 위해 너무 많이 교환하는 낭비가 발생할 수도 있습니다.

아래와 같은 8개의 숫자가 임의의 순서로 나열되어 있습니다.

이 숫자들을 오름차순으로 정렬하기 위해 바로 옆의 있는 숫자들과 비교하는 방법을 사용해 보겠습니다.

 

6 3 8 5 2 7 4 1

 

먼저 가장 앞의 6과 3을 비교해서 순서를 바꿉니다.

 

교환 전: 6 3 8 5 2 7 4 1

교환 후: 3 6 8 5 2 7 4 1

 

다음 쌍인 6과 8을 비교해보면 교환할 필요가 없으므로 그대로 둡니다.

바로 다음에 있는 쌍인 8과 5를 비교해서 순서를 바꿉니다.

 

교환 전: 3 6 8 5 2 7 4 1

교환 후: 3 6 5 8 2 7 4 1

 

이런 식으로 숫자 끝까지 진행하면 아래와 같이 정렬이 됩니다.

 

3 6 5 2 7 4 1 8

 

하지만 아직 오름차순으로 정렬이 되지 않았기 때문에, 다시 처음부터 동일한 작업을 반복합니다.

 

3 6 5 2 7 4 1 8

3 6 5 2 7 4 1 8 (교환)

3 5 6 2 7 4 1 8 (교환)

3 5 2 6 7 4 1 8 

3 5 2 6 7 4 1 8 (교환)

3 5 2 6 4 7 1 8 (교환)

3 5 2 6 4 1 7 8

 

조금 더 잘 정렬이 되었습니다. 이 과정을 끝까지 반복하면 최종적으로 아래와 같이 오름차순 정렬이 될 것입니다.

 

1 2 4 3 5 6 7 8

 

이러한 정렬 방식을 ‘버블 정렬’이라고 합니다.

마치 거품이(비교 및 교환이) 터지면서 위로 올라오는 (배열의 옆으로 이동하는) 방식이기 때문입니다.

아래와 같이 의사 코드로 나타낼 수 있습니다.

Repeat n–1 times

    For i from 0 to n–2

        If i'th and i+1'th elements out of order

            Swap them

중첩 루프를 돌아야 하고, n개의 값이 주어졌을 때 각 루프는 각각 n-1번, n-2번 반복되므로  (n-1)*(n-2) = n^2-3n+2(n−1)∗(n−2)=n​2​​−3n+2  번의 비교 및 교환이 필요합니다.

여기서 가장 크기가 큰 요소는 n^2 이므로 위와 같은 코드로 작성한 버블 정렬 실행 시간의 상한은 O(n^2)이라고 말할 수 있습니다.

정렬이 되어 있는지 여부에 관계 없이 루프를 돌며 비교를 해야 하므로 위와 같은 코드로 작성한 버블 정렬의 실행 시간의 하한도 여전히 O(n^2)이 됩니다.

정렬이 되어있지 않을 경우 또다시 정렬을  하게되는 버블 정렬을 했을때 같은 행위를 반복하므로 버블 정렬이 비효율적이나

정렬이 되어있을 경우 효율적이다.

버블 정렬(bubble sort) 알고리즘의 특징

 

장점
구현이 매우 간단하다.

 

단점
순서에 맞지 않은 요소를 인접한 요소와 교환한다.
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.
버블 정렬(bubble sort)의 시간복잡도
시간복잡도를 계산한다면

비교 횟수
최상, 평균, 최악 모두 일정
n-1, n-2, … , 2, 1 번 = n(n-1)/2
교환 횟수
입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
입력 자료가 이미 정렬되어 있는 최상의 경우, 자료의 이동이 발생하지 않는다.
T(n) = O(n^2)

관련 POST

• 선택 정렬(selection sort)
• 삽입 정렬(insertion sort)
• 셸 정렬(shell sort)
• 합병 정렬(merge sort)
• 퀵 정렬(quick sort)
• 힙 정렬(heap sort)