(C++) 칵테일 쉐이크 정렬 - (ADL 추가)

C++

#include <iostream>

#include <time.h>

using namespace std;

const int TRUE = 1;

const int FALSE = 0;

inline void swap(int a[] , int x1 , int x2){

    int temp = a[x1] ; a[x1] = a[x2] ; a[x2] = temp;

}

int N = 50000;                                  // 데이터 갯수

void Shaker_Sort(int *arr)

{

    int shift = 0 , sort = TRUE;

    int left = N, right = 1;                    // 왼 / 오

    

    while(TRUE)

    {

        for(int i = right; i<left;i++)          // Bubble 정렬 정방향

        {

            if(arr[i] > arr[i+1])

            {

                swap(arr, i, i+1);

                sort = FALSE;

            }

        }

        --left;

        if(sort == TRUE) return;                // 정렬이 한번도 안일어났다면 바로 종료

        sort = TRUE;

    

        for(int i = left; i > right;i--)        // Bubble 정렬 역방향

        {

            if(arr[i] < arr[i-1])

            {

                swap(arr,i , i-1);

                sort = FALSE;

            }

        }

        ++right;

        if(sort == TRUE) return;

        sort = TRUE;

    }

}

int main()

{

    int arr[N];

    double start_time;

    srand(time(NULL));

    for(int i=1;i<=N;i++)

        arr[i] = rand() % 10001;

    start_time = clock();                   // 정렬하기전 시작시간 저장

    Shaker_Sort(arr);

    cout << "칵테일 쉐이커 정렬 실행 시간 = " << (clock()-start_time)/(CLOCKS_PER_SEC) << "초" <<endl;     // 정렬이 끝난 후 시간 - 정렬하기전 시작시간을 빼서 걸린시간 측정

    //for(int i=1;i<=N;i++)

    //    cout << arr[i] << " ";

    return 0;

}

ADL 

칵테일 쉐이크 정렬 – ADL

Shaker_Sort(arr[], N)

Sort  ← 1;// 1 = TRUE , 0 = FALSE

left  ← N;// N = 데이터 개수

right ← 1;

while(right > left) do {

for (i ← right; I < left; i ← i+1) do {

if (arr[i] > arr[i+1]) then {

temp ← arr[i];

arr[i] ← arr[i+1];

arr[i+1] ← temp;

}

}

left ← left – 1;

for (i ← left; i > right; i ← i-1) do {

if (arr[i] < arr[i-1]) then {

temp ← arr[i];

arr[i] ← arr[i-1];

arr[i-1] ← temp;

}

}

right ← right + 1;

}

end Shaker_Sort(arr[], N)

칵테일 정렬의 성능은 최상의 경우 O(n) , 최악의 경우 O(n^2)