I'm taehee.won.

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

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

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

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

 다음과 같이 구현하였다.

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

 거품 정렬 (Bubble sort) 은 인접한 두 개의 데이터를 비교하는 것을 반복하여 정렬하는 방법이다. 데이터가 많아질 수록 많은 시간이 걸리지만, 코드가 단순하여 구현하기 쉽다. 거품이라는 이름은 데이터가 거품이 수면으로 올라가듯 정렬되는 모습에서 지어진 이름이다.

 위의 그림과 같은 단계를 통해서 정렬이 진행된다. 처음부터 시작해서 인접한 데이터를 비교해서 큰 값이 뒤에 위치하도록 한다. 데이터 전체를 한번 반복하게 되면, 가장 큰 값이 수의 집합에서 마지막에 위치하게 된다. 그럼 마지막에 위치한 값을 빼고 다시 처음부터 같은 방식으로 정렬한다. 이 방식은 항상 같은 비교 횟수((n-1) + (n-2) + (n-3) ... + 2 + 1 = n * (n-1)/2 = n(n-1)/2)를 가지게 된다.

 거품 정렬을 다음과 같이 구현하였다.

 비교는 항상 다음 위치의 값과 비교되므로, 데이터 집합의 처음부터 마지막에서 한개 전의 데이터까지 반복한다. Temp_Complete 는 Step 에 따라 줄어드는 데이터 집합의 크기를 저장하며, iTemp_Compare 가 증가하며, 값을 비교하며 정렬한다.

 아래의 함수는 비교 이후, 두개의 값이 바뀌어야 할 때에 값을 바꾸어 주는 Swap 함수이다.

 거품 정렬을 사용하는 예제이다.

 앞으로의 정렬 예제에서는 위의 정수형 배열의 값을 출력하는 출력함수를 이용하여, 정상적으로 정렬이 되었는지 확인한다.

 "4, 2, 1, 5, 3, 8, 5, 3, 1, 4" 의 데이터 집합을 만들고, 거품 정렬을 이용하여 정렬한다.

 위와 같이 올바르게 정렬된 것을 확인할 수 있다.

 거품 정렬은 추가적인 메모리 사용이 없는 대신, 효율이 좋지 않다. 이를 개선하였다.

 위의 그림을 보면, Step 1 에서 2 번의 비교 후, 데이터 위치 교체를 하고나면, 더 이상의 교체는 일어나지 않는다. 데이터 위치 교체 이후의 값들은 이미 데이터 집합에서 최대값이 순서대로 정렬되어 있음을 의미한다. 3 번째에서부터 7 번째까지의 비교 연산은 다음 Step 부터는 필요가 없다. 이를 개선했을 경우에는 데이터 집합의 후반부에 정렬되어 있는 값들은 다시 비교하지 않아 효율을 올릴 수가 있다.

 다음과 같이 거품 정렬을 개선하여 구현하였다.

 iTemp_LastSwap 변수를 추가하여, 데이터 교체가 일어났을 때의 위치를 저장하였다가 다음 단계로 넘어갈 때에, 사이즈를 증가시켜서 다시 비교하여 정렬할 필요가 없는 구간을 다시 비교하지 않도록 개선하였다.