[C] 칵테일 정렬 (Cocktail Sort) 정의 / 코드

 칵테일 정렬을 한마디로 표현하면, 거품 정렬의 최종 개선판이라고 할 수 있다.

 앞서 개선한 거품 정렬은 한번 비교가 필요없는 데이터 구간이 결정되면 단계마다 그만큼의 연산이 줄어들기 때문에 효율이 좋아지지만, 한번 비교 연산이 줄어들고 나면, 추가적인 효율이 크게 발생하기 어렵다.

 

 추가적으로 큰 효율 증가를 기대하기 위해서 거품 정렬을 이전에 한 것과 반대 방향으로 이용하는 방식을 번갈아 사용하도록 개선한다.

 위의 그림과 같이 데이터 집합을 한번은 순서대로 거품 정렬하고, 한번은 역순으로 거품 정렬하는 방식으로 정렬을 하며, 앞서 개선한 방법을 이용하여 더 이상 정렬이 필요없는 구간을 다시 비교하지 않도록 한다.

 

 다음과 같이 구현하였다.

 기존에 For 구문이 한 단계씩 진행되는 것이었다면, While 구문으로 두 단계씩 묶어서 정렬한다. 거품 정렬과 동일한 방식으로 인접한 두 개의 데이터를 비교하는 것을 반복하여 정렬한다. 정렬할 때에 사용하는 Swap 함수, 이 정렬 사용하는 예제는 이전 글(링크 : [C] 거품 정렬 (Bubble Sort) 정의 / 코드 / 개선)에서 확인할 수 있다.