Bubble Sort: 버블 정렬

* Bubble Sort?

 

이미지 출처ㅣ https://priestlandscs.com/standard-sorting-algorithms/

버블 정렬은 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 버블 정렬을 오름차순으로 한 번 실행하였다면, 리스트의 가장 오른쪽 끝에는 제일 큰 수가 들어가게 된다. 오른쪽부터 정렬이 완료되며 정렬이 되지 않은 왼쪽을 반복하여 정렬하면 정렬이 완료된다. 

 

 

* Pseudocode

버블 정렬의 슈도 코드

하나의 스캔은 index = 0 부터 index = i - 1 까지 반복하는 루프로 구성된다. index 번째 요소와 index + 1 번째 요소를 비교하여 둘이 크다면 swap 한다. 이러한 스캔 과정이 n - 1번 반복되면 정렬은 완료된다. 

 

* 분석

버블 정렬의 비교 횟수는 항상 최선, 평균, 최악 아무튼 어떤 경우에도 언제나 똑같다. 비교 횟수는 n - 1 + n - 2 + ,,, + 1 이므로 N*( N  + 1) / 2 가 되고 시간 복잡도는 n^2가 된다. 이동 횟수는 최악의 경우 입력 자료가 역순으로 정렬되어 있어 그 이동 횟수는 비교 횟수 * 3이 될 것이다. 왜냐하면 모든 원소를 바꾸어주어야 하기 때문이다. 그러나 어쩄든 n^2의 시간복잡도를 가질 것이다. 최선의 경우는 모든 자료가 이미 정렬되어 있는 경우로 이런 경우에는 0번의 이동 횟수를 가진다. 

버블 정렬의 장점은 코드가 단순, 간단하여 이해가 빠르다는 점이다. 

단점으로는 순서에 맞지 않은 요소를 인접한 용소와 교환한다는 것이다. 하나의 요소가 가장 왼쪽에서 제일 오른쪽으로 이동하기 위해서는 배열 안의 모든 요소와 바꾸며 하나하나 뒤로 가야 한다. 굉장히 비용이 많이 드는 방식이라고 할 수 있다. 이러한 과정에서 특정 요소가 제 자리에 있음에도 다시 교환이 이루어지는 희생이 발생될 수 있다. 따라서 버블 정렬은 잘 사용되지 않는다. 

 

* 버블 정렬의 시간 복잡도는 O(n ^ 2)