자료구조 :: 정렬(3) 쉐이커 정렬, 퀵 정렬

# 쉐이커 정렬(shaker sort)

버블 정렬에서의 비효율적인 부분을 개선한 정렬.
리스트의 왼쪽부터 검사해서 마지막으로 교환을 수행한 위치를 저장하여 다시 이부분을 기준으로 오른쪽 부터
리스트의 왼쪽까지 반대로 검사하는 방식이다. 양쪽을 번갈아가면서 정렬을 하기 때문에 칵테일 정렬 또는
양방향 거품 정렬등으로도 불리운다.


# 퀵 정렬(quick sort)

퀵 정렬은 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬이다.
리스트에 대해 적당한 값(pivot)을 기준으로 이보다 작거나 같은 값을 왼쪽, 크거나 같은 값을 오른쪽에
오도록 재배열 하고 나누어진 리스트에 대해 다시 같은 과정을 반복적으로 정렬 하는 방법이다.

퀵 정렬은 속도가 빠르고 추가 메모리 공간을 필요로 하지 않는등의 장점이 있는 반면 정렬된 리스트에
대해서는 오히려 수행시간이 더 많이 걸리는 등의 단점도 가진다.

퀵 정렬의 복잡도 : O(nlog₂n) (평균)


ShakerSort_QuickSort.cpp

#include <stdio.h> 
#include <stdlib.h> 
#include <time.h> 

#define random(n) (rand()%n) 
#define SWAP(x,y,t) ((t) = (x),(x) = (y),(y) = (t)) 

void ShakerSort(int *list, int n) 
{ 
int i,j,temp; 
int left,right,shift; 

    left=0; 
    right=n-1; 

while(left<right) 
    { 
for(i=left;i<right;i++) 
        { 
if(list[i]>list[i+1]) 
            { 
                SWAP(list[i],list[i+1],temp); 
                shift=i; // 마지막으로 교환이 발생한 인덱스 저장
            } 
        } 
        right=shift; // 마지막 교환 인덱스 값을 right값에 대입

for(i=right;i>left;i--) 
        { 
if(list[i]<list[i-1]) 
            { 
                SWAP(list[i],list[i-1],temp); 
                shift=i; // 마지막으로 교환이 발생한 인덱스 저장
            } 
        } 
        left=shift; // 마지막 교환 인덱스 값을 left값에 대입
    } 
} 

void QuickSort(int *list, int left, int right) 
{ 
int i,j,pivot,temp; 

if(left<right) 
    { 
        i=left; 
        j=right+1; 

        pivot=list[left]; // pivot은 리스트의 첫번째 값

do{ 
while(list[++i] < pivot); // left부터 pivot값보다 작은값을 찾는다
while(list[--j] > pivot); // right부터 pivot값보다 작은값을 찾는다

if(i < j) 
                SWAP(list[i],list[j],temp); // 검색한 인덱스 교환
        }while(i < j); 

        SWAP(list[left],list[j],temp); // pivot의 자리를 변경

// pivot을 기준으로 반으로 나누고 각각을 재귀 호출로 반복 정렬 한다
        QuickSort(list,left,j-1);  
        QuickSort(list,j+1,right);         
    } 
} 
void ScreenOut(int *pList, int count) 
{ 
int i; 
for(i=0;i<count;i++) 
        printf("%d ",pList[i]); 

    puts(""); 
} 

int main() 
{ 
int i,input; 
int *list; 

    srand(time(NULL)); 

    printf("Input Data Count : "); 
    scanf("%d",&input); 

    list=(int *)malloc(sizeof(int)*input); 

for(i=0;i<input;i++)     
        list[i]=random(100); 

    printf("Insert Data : "); 
    ScreenOut(list,input); 

    ShakerSort(list,input); 

    printf("Sorting Data : "); 
    ScreenOut(list,input); 

for(i=0;i<input;i++)     
        list[i]=random(100); 

    printf("Insert Data : "); 
    ScreenOut(list,input); 

    QuickSort(list,0,input-1); 

    printf("Sorting Data : "); 
    ScreenOut(list,input); 

    free(list); 

return0; 
}