지난번에는 배열이 미리 정렬되어 있다는 것으로 가정하고 실습을 했었다. 오늘은 그 전제가 되었던 버블 정렬(Bubble sort)에 대해서 공부했다.
#include <cs50.h>
#include <stdio.h>
int main(void)
{
int numbers[6] = {4, 8, 15, 16, 23, 42}; // 오름차순 정렬을 전제로...
...
}1. Sort 아이디어
여러 숫자가 뒤죽박죽 섞여 있다. 이때 오름차순으로 정렬하고 싶다고 가정해보면, 두 개의 인접한 값을 비교하면서 위치를 교환하는 방식으로 정렬하면 효과적일 것이다. ①부터 확인해보면 되는데, 해당 값(①)의 왼쪽에 있는 값(6)과 비교했을 때 해당 값(①)이 더 큰 값이 맞으면 가만히 있고, 그게 아니면 교환환다. ②를 ①과 비교하고 ③을 ②와 비교하는 방식으로 ⑦까지 한다. 한바퀴 돌아도 아직 오름차순 정렬이 되지 않았기 때문에 다시 처음부터 똑같은 작업을 해준다.
위 작업을 하다보면 8이 계속 오른쪽으로 움직인다. 거품이 떠오르듯 8이 왼쪽에서 오른쪽으로 움직이고 7도 왼쪽에서 오른쪽으로 거품처럼 움직인다고 해서 버블 정렬이다.
2. Psudo Code
Repeat (n - 1) times
For i from 0 to (n - 2) // 0부터 (n - 2)이니까 총 (n - 1)번 순환
If i'th and i+1'th elements out of order
Swap them3. 버블 정렬 실행 시간의 Big O 표기
(n - 1) * (n - 1) // 바깥 반복문은 n - 1번 반복하고 안쪽 반복문도 n - 1번 반복한다
n^2 - 2n + 1
O(n^2) // 지수가 가장 큰 n^2의 영향력이 가장 크기 때문에 이렇게 표기할 수 있다계산에서 보듯이 버블 정렬은 지지난 시간에 봤었던 상한선 목록의 맨 위에 놓인다. 즉, 버블 정렬은 선형 검색이나 이진 검색보다 더 많은 시간이 든다.
| Big O notation | 내용 |
|---|---|
| O(n^2) | 버블 정렬 |
| O(n log n) | |
| O(n) | 선형 검색 |
| O(log n) | 이진 검색 |
| O(1) |
그래서 선형 검색과 이진 검색(전화번호부) 중 이진 검색이 더 빨랐기 때문에 이진 검색을 더 좋은 알고리즘이라고 할 수도 있다. 하지만 이진 검색의 전제는 정렬이기 때문에, 꼭 이진 검색이 더 좋다고 하는 것은 맞지 않다(심지어 더 느릴 수도 있다고 한다).
4. Big Ω 는??
정렬 알고리즘에서 가장 좋은 입력값은 이미 정렬되어 있는 것이다. 하지만 버블 정렬은 이미 정렬되어 있어도 정렬을 시도한다. 그래서 좋은 입력값이 주어져도 크게 달라지는 것은 없다.
그래서 버블 정렬의 하한선은 n^2이다.
| Big Ω notation | 내용 |
|---|---|
| Ω(n^2) | 버블 정렬 |
| Ω(n log n) | |
| Ω(n) | 배열 안에 존재하는 값의 개수 세기 |
| Ω(log n) | |
| Ω(1) | 선형 검색, 이진 검색 |
