[CS50] 알고리즘 - 버블 정렬

버블 정렬

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

 

정렬 알고리즘 중 하나는 버블 정렬이 있다.

 

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

 

단 두 개의 요소만 정렬해주는 좁은 범위의 정렬에 집중하는 접근법이다.

 

간단한 방법이지만 단 하나의 요소를 정렬하기 위해 교환을 너무 많이 시도해 낭비가 발생할 수 있다.

 

 

버블 정렬의 예시

아래와 같은 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 3 4 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^2이므로 버블 정렬의 실행 시간의 상한은 O(n^2)이다.

 

정렬 여부와 상관없이 모든 요소를 비교해야 하므로 실행 시간의 하한도 Ω(n^2)이다.

 

 

정렬 알고리즘 관련 설명은 아래 포스팅에 더 자세하게 나와있다.

 

https://laurent.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0-%EB%B2%84%EB%B8%94-%EC%A0%95%EB%A0%AC-bubble-sort

[자료구조] 버블 정렬 (bubble sort)

 

 

 

References

모두를 위한 컴퓨터 과학 (CS50 2019)

모두를 위한 컴퓨터 과학 (CS50 2019)