Bubble sort는 정렬되는 방식이 마치 거품이 수중에서 수면으로 올라가는 모습과 같다고 하여 붙여진 이름이다.
간단히 예를 보여 설명하겠다
2 5 1 4 3 초기상태
2 5 1 4 3 4번째 원소와 5번째 원소를 비교하여 앞의 원소가 더 크면 교환한다 (교환)
2 5 1 3 4 3번째 원소와 4번째 원소를 비교하여 앞의 원소가 더 크면 교환한다 (교환하지 않는다)
2 5 1 3 4 2번째 원소와 3번째 원소를 비교하여 앞의 원소가 더 크면 교환한다 (교환)
2 1 5 3 4 1번째 원소와 2번째 원소를 비교하여 앞의 원소가 더 크면 교환한다 (교환)
1 2 5 3 4 첫번째 원소가 오름차순으로 정렬됨
위의 예는 한개의 원소를 정렬하는 주기이고, 이를 원소의 개수만큼 반복 수행하면 모든 원소가 오름차 순으로 정렬된다
그림을 통한 이해를 돕기위해 다음 사이트를 추천한다.
http://www.sorting-algorithms.com/bubble-sort
정렬 방식을 완전히 이해했다면 다음을 읽어보자
bubble sort는 시간복잡도(Time Complexity)가 O(n^2)으로 merge sort나 quick sort에 비해서 시간 복잡도가 크지만 많이 사용되는 sorting algorithm 중 하나이다.
그 이유는
1. 구현이 쉽다는 점 때문이다.
위에서 언급한 O(n log n)의 시간복잡도를 가진 알고리즘들과 비교했을 때 input data가 적으면 실제로 그 속도가 거의 비슷하기 때문에 구태여 어려운 알고리즘을 사용 할 이유가 없는 것이다.
2. input data가 적은 경우에는 quick sort나 merge sort가 오히려 더 느릴 수도 있다.
대부분 quick이나 merge sort는 recursive call로 구현하기 때문에 function call에 의한 overhead가 있는데 input data가 적은경우 그 overhead가 차지하는 부분이 상대적으로 크기 때문에 시간복잡도가 우수하더라도 더 낮은 performance를 보일 수도 있다.
3. bubble sort는 거의 정렬된 상태(nearly sorted)에서 O(n)의 시간복잡도를 가진다.
반면에 merge와 quick sort는 여전히 O(n log n)의 시간복잡도를 보인다.
이를 구현하기 위해서는 bubble sort에서 한 원소를 정렬하는 주기동안 원소간의 교환(swap)이 한번도 일어나지 않은 경우 정렬되었다고 판단하는 로직을 추가해야한다.
이러한 이유로 우리는 O(n^2)의 sorting algorithm을 배우는 것이다.
앞으로 나올 selection과 insertion sort도 각각의 정렬이 가지는 장점과 유리한 상황들을 생각하면서 공부하는게 좋다.
C언어를 이용한 소스는 조만간 업데이트