칵테일 정렬

Description

칵테일 정렬은 버블 정렬에서 한단계 개선된 정렬이다.
양방향버블정렬 또는 셰이커정렬이라고도 불리운다.
정렬 방식은 버블 정렬과 같되 왼쪽과 오른쪽을 왕복한다.
시간 복잡도 = O(N^2) 이다

우선, 버블정렬 처럼 왼쪽에서 시작한다. (버블정렬과 정렬방식이 같음으로 자세한 설명은 생략한다)

여기까지는 버블과 같다, 우측에서부터 정렬 하되 확정된 숫자 9는 제외하고 시작한다.
우측에서 시작 할땐 작은 수가 왼쪽으로 가도록 정렬하면 된다.

6과 1을 비교한다, 더 작은 수인 1이 왼쪽에 있기때문에 자리 바꿈은 없다.

1과 3을 비교한다, 작은 수인 1을 왼쪽으로 가도록 3과 자리를 바꾼다

1과 4를 비교한다, 1과 4의 자리를 바꾼다.

8과 1의 자리를 바꾼다.

7과 1의 자리를 바꾼다.

5와 1의 자리를 바꾼다.

2와 1의 자리를 바꾼다. <br

이제 1의 자리가 확정되었다.
또 다시 좌측에서 시작하여 정렬하고 끝나면 우측에서 정렬을 시작하고 돌아와 숫자가 각각 하나씩
끝에서부터 확정되어가는 방식이다.

---

Cord

#include <iostream>

#define LENGTH 9 // 배열의 길이

using namespace std;

int main()
{
    int dataArr[LENGTH] = { 2, 5, 7, 8, 4, 9, 3, 1, 6 };
    
    int evenCount = 0;  // 짝수 실행 수
    int oddCount = 0;   // 홀수 실행 수
    int temp;
    bool flag = true;   // 정렬 중단 스위치

    // Cocktail sort 실행
    for (int idx = 0; idx < LENGTH; idx++)
    {
        flag = true;
        if (idx % 2 == 0) // 짝수 일때
        {
            for (int even = 0 + oddCount; even < LENGTH - 1 - evenCount; even++)
            {
                // 왼쪽에 있는 수가 오른쪽 보다 크면 자리 바꾸기 (큰 수를 오른쪽으로)
                if (dataArr[even] > dataArr[even + 1])
                {
                    temp = dataArr[even];
                    dataArr[even] = dataArr[even + 1];
                    dataArr[even + 1] = temp;
                    flag = false;
                }
            }
            evenCount++;
        }
        else // 홀수 일때
        {
            for (int odd = LENGTH - 1 - evenCount; odd > 0 + oddCount; odd--)
            {
                // 오른쪽에있는 수가 왼쪽 수보다 작으면 자리 바꾸기 (작은 수를 왼쪽으로)
                if (dataArr[odd] < dataArr[odd - 1])
                {
                    int temp = dataArr[odd - 1];
                    dataArr[odd - 1] = dataArr[odd];
                    dataArr[odd] = temp;
                    flag = false;
                }
            }
            oddCount++;
        }

        // 더 이상 정렬 할 숫자가 없으면 끝내기
        if (flag) { break; }
    }

    // 결과 출력
    string result;
    for (int idx = 0; idx < 9; idx++)
    {
        if (idx == 8)
        {
            result += dataArr[idx] + '0';
        }
        else
        {
            result += dataArr[idx] + '0';
            result += ", ";
        }
    }
    cout << "data = {" << result << " }";
    cout << "\n\n\n\n\n\n\n";
    return 0;
}

---

Result