정렬 - 퀵 정렬(Quick Sort)

퀵 정렬은 많이 사용되는 정렬 중 하나이다.

 

퀵 정렬은 임의의 Pivot 값을 선정하고 Pivot값보다 큰 값과 작은 값을 나눠 정렬하는 방식이다.

 

오름차순을 이용하여 설명하면,

 

먼저, 외쪽에서 오른쪽으로 피봇값보다 큰 값을 찾을 때까지 우측으로 이동하고,

 

다음, 오른쪽에서 왼쪽으로 피봇보다 작은 값을 찾을때까지 좌측으로 이동하여,

 

처음 발견되는 값들을 서로 Swap한다.

 

그런 과정을 지속적으로 반복하여 정렬하여 준다.

 

내림차순은 조건을 반대로 해줌으로써 할 수 있다.

 

퀵 정렬은 재귀호출을 사용하여 이용함으로써 간편하게 해답을 찾을 수 있다.

 

Quick_Sort.

 

#ifdef _QUICK_SORT_ 
#endif _QUICK_SORT_ 

//오름차순  
void Asc_Quick_Sort(int data[], int left, int right);    
int Asc_Part_Quick_Sort(int data[], int left, int right);
 
//내림차순 
void Des_Quick_Sort(int data[], int left, int right);
int Des_Part_Quick_Sort(int data[], int left, int right);
 
void Swap(int *left, int *right);
void Prt_Quick_Sort(int data[], int size);
 

Quick_Sort.c

#include<stdio.h> 
#include"Quick_Sort.h"
 
void Asc_Quick_Sort(int data[], int left, int right)
 { 
    int pivot; 
    int i;     

    if(left<right) 
    { 
        pivot=Asc_Part_Quick_Sort(data, left, right);        //기준 피봇을 데이터의 가장 우측에 있는 데이터로 선정
         Asc_Quick_Sort(data, left, pivot-1);                //좌측 끝부터 피봇 전까지
         Asc_Quick_Sort(data, pivot+1, right);            //기준 우측부터 우측 끝까지
     } 
} 

int Asc_Part_Quick_Sort(int data[], int left, int right)
 { 
    int pivot = right; 

    while(left<right) 
    { 
        while((data[left]<=data[pivot])&&left<right) left++;
         while(data[right]>=data[pivot]&&left>right) right--;
         if(left<right) Swap(&data[left], &data[right]);
     } 
     
    Swap(&data[right], &data[pivot]); 

    return right; //최종 오른쪽 피봇 반환
 } 

void Des_Quick_Sort(int data[], int left, int right)
 { 
    int pivot; 
    int i;     

    if(left<right) 
    { 
        pivot=Des_Part_Quick_Sort(data, left, right);        //기준 피봇을 데이터의 가장 우측에 있는 데이터로 선정
         Des_Quick_Sort(data, left, pivot-1);                //좌측 끝부터 피봇 전까지
         Des_Quick_Sort(data, pivot+1, right);            //기준 우측부터 우측 끝까지
     } 
} 

int Des_Part_Quick_Sort(int data[], int left, int right)
 { 
    int pivot = right; 

    while(left<right) 
    { 
        while((data[left]>=data[pivot])&&left<right) left++;
         while(data[right]<=data[pivot]&&left>right) right--;
         if(left<right) Swap(&data[left], &data[right]);
     } 

    Swap(&data[right], &data[pivot]); 

    return right; //최종 오른쪽 피봇 반환
 } 

void Swap(int *left, int *right)
 { 
    int temp=*left; 
    *left=*right; 
    *right=temp; 
} 

void Prt_Quick_Sort(int data[], int size)
 { 
    int i=0;
     for(i;i<size;i++) 
        printf("%d\t", data[i]); 
}