[CS50] 버블 정렬

어떤 배열이 있을 때 그 배열이 이미 정렬되어있는 배열이라면 훨씬 빠른 속도로 검색이 가능합니다. 정렬하기 위한 방법은 여러 가지가 존재하고 각각 실행시간도 차이가 있습니다. 오늘은 정렬 기법 중 하나인 버블 정렬에 대해 공부해보도록 하겠습니다.

 

버블정렬

사실 이러한 정렬이 있다는 건 알고 있었지만 버블 정렬이라고 불리는지는 몰랐습니다. ㅎㅎ

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

버블정렬은 단 두개의 요소만 정렬해주는 좁은 범위의 정렬에 집중하기 때문에 간단하지만 하나의 요소를 정렬하기 위해서 많은 낭비가 발생할 수 있습니다.

예를 들어 설명하자면

6 4 3 7 1 2 8 5 라는 순서의 숫자가 있습니다. 이를 오름차순으로 정렬하고자 할 때 버블 정렬을 사용한다면

1.   4 6 3 7 1 2 8 5

2.   4 3 6 7 1 2 8 5

3.   4 3 6 1 7 2 8 5   // 6과 7을 비교했을 때 교환할 필요가 없으므로 다음 숫자인 7과 1을 비교해서 바꿔줍니다.

4.   4 3 6 1 2 7 8 5

5.   4 3 6 1 2 7 5 8  // 이렇게 한 번의 사이클이 돌게 됩니다.

...                         // 이런 식으로 다시 처음부터 숫자 끝까지 진행한다면

n.   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)이 됩니다.

따라서 버블 정렬의 경우 요소가 작을 때는 효율적이라고 볼 수 있지만 요소가 커지면 커질수록 비효율적이라고 볼 수 있습니다.

 

---

출처

본 내용은 CS50의 2019년 강의를 듣고 작성했습니다. (개념이 어느 정도 정리되면 최신강의도 다시 듣고 수정할 내용 있으면 수정하겠습니다.)

 

강의 자료는 EdX에서 무료로 사용할 수 있고 boostcourse에서 한글 강의로도 들을 수 있습니다.