※ stdlib.h 파일에는 qsort() 라는 훌륭한 함수가 존재한다. 해당 함수를 활용하여도 무방하다.

※ 함수 설명
두 함수 모두 비재귀 형식의 퀵소트이며
- quick_sort1() 함수는 : 세값의 중위 분할을 통한 퀵소트로, 삽입정렬을 사용한다.
- quick_sort2() 함수는 : 난수 분할을 통한 퀵소트이며, 삽입정렬을 사용한다.

이 첨부 파일에 있는 건 일반적인 함수의 형태이다. (int형 뿐 아니라 모든 형태의 자료형을 비교할 수 있도록 만든 것이다)
자료 배열의 선두 번지인 base,
자료의 개수 nelem,
레코드의 크기 width,
키값의 비교를 하는 함수 포인터 fcmp 를 뜻한다.
fcmp 함수는
int intcmp(const void *a, const void *b) 등을 뜻한다.


■ 퀵 정렬 개념

주어진 입력 리스트를 피봇(pivot) 또는 제어키(control key)이라 불리는 특정 키 값보다 작은 값을 가지는 레코드들의 리스트와 큰 값을 가지는 레코드들의 리스트로 분리한 다음, 이러한 두 개의 서브 리스트들을 재귀적으로 각각 재배열하는 과정을 수행하는 방식
퀵 정렬 방법은 하나의 커다란 입력 데이터의 집합을 정렬하는 것보다는 두개의 작은 입력 데이터들을 정렬하는 것이 빠르다는 일반적인 사실에 바탕을 둠
분할 및 정복 방법 사용
피봇(Pivot)이라 부르는 특정한 데이터를 기준으로 피봇보다 작은 값을 가진 데이터들은
배열의 왼쪽 부분에, 큰 값을 가진 데이터는 오른쪽에 위치하도록 배열
퀵 정렬은 기본적으로 순환(recursive) 알고리즘 형태를 취하며, 오름차순으로 정렬할 경우 레코드 R1을 제어 키 또는 피봇 키로 하여 왼쪽으로 가면서 R1보다 큰 키 값을 찾고, 오른쪽으로부터 왼쪽으로 가면서 R1보다 작은 키 값을 찾아 서로 교환한다. 위의 과정이 수행될 때 오른쪽과 왼쪽이 서로 교차하면 중지하고 R1을 제일 나중에 찾은 R1보다 작은 키 값과 교환하면 R1보다 작은 키 값을 갖는 레코드들과 큰 키 값을 갖는 레코드들로 분할되어 하나의 파일이 제어키 R1을 기준으로 두 개의 서브 파일로 재배열된다. 재배열된 서브파일에 대해 독립적으로 위의 수행 과정을 반복하면 정렬이 완료된다.

■ 퀵 정렬 알고리즘 단계 : 분할과 정복 방식
① 피봇(Pivot) : 정렬할 데이터 S에서 하나 v를 선택한다.
② 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
③ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}



■ 특징
▷ 평균 연산 시간에 있어서 내부 정렬 방법 중 가장 우수
     - 실제 수행속도가 가장 빠른 정렬 알고리즘
▷ 스택 공간을 사용
▷ 재귀 호출을 기반으로 동작

■ 퀵 정렬 알고리즘

-----------------------------------------------------------------------------
void Quicksort(int A[], int N) {Qsort(A,0, N-1); }      /* 퀵 정렬 호출 함수 */

int Median3(int A[], int Left, int Right)                       /* 세 수의 중위수 계산 함수 */
{      int Center= (Left + Right) / 2;              /* A[Left]<= A[Center]<= A[Right]*/
        lf( A[Left] > A[Center] ) Swap( &A[Left], &A[Center] );
        if( A[Left] > A[Right] )  Swap( &A[Left], &A[Right] );
        if( A[Center] > A[Right]) Swap(&A[Center], &A[Right]);
        swap( &A[Center], &A[Right-1] );   /* 피봇된 수를 오른쪽-1의 위치에 있는 수와 SWAP */
        return A[Right-1];                            /*return 피봇 */
}

#define Cutoff(3)                                                     /* 퀵 정렬 함수 */
void Qsort( int A[], int Left, int Right )       /* 배열 A의 왼쪽 끝 첨자:Left, 오른쪽 끝 첨자:Right */
         {     int i, j, Pivot;                              
/*1*/       if( Left + Cutoff <= Right )          
/*2*/       {     Pivot = Median3( A, Left, Right);  
/*3*/              i=Left; j=Right-1;
/*4*/              for( ; ; )
/*5*/             {    while( A[++i ] < Pivot ){}
/*6*/                   while( A[--j ] > Pivot ){}
/*7*/                   if( i < j )
/*8*/                        swap( &A[ i ], &A[ j ] );
/*9*/                   else   break;
                      }
/*10*/            swap( &A[ i ], &A[ Right-1] );
/*11*/            Qsort( A, Left, i-1 );
/*12*/            Qsort( A, i+1, Right );  
                }
                else                            
/*13*/           InsertionSort( A+Left , Right-Left+1)        
           }



②세 수의 중위수 계산, Pivot에 중앙값 넣기
⑤배열의 왼쪽에서부터 중앙값보다 큰 원소까지
   이동
⑥배열의 오른쪽에서부터 원소의 값이 중앙값보다
   작은 원소까지 이동
⑦⑧⑨정렬이 끝나지 않았으면 중앙값보다 작은
   원소는 왼쪽에, 큰 원소는 오른쪽에 들어가도록
   교체함. 정렬이 끝났으면 무한루프를 벗어남
⑩중앙값보다 큰 첫 번째 요소와 중앙값을 교환해
   중앙값을 작은 값과 큰 값 사이에 끼워 넣음.
   중위치 정렬
⑪왼쪽부분리스트(중앙값보다 작은부분)의 퀵정렬
⑫오른쪽부분리스트(중앙값보다 큰부분)의 퀵정렬
⑬원소가 Cutoff보다 작거나 같은 서브트리의
   삽입정렬
-----------------------------------------------------------------------------



■ 성능

▷ 최악의 경우: O(n2)
▷ 평균: O(nlogn)
▷ 최선의 경우는 n 개의 데이터가 저장된 배열이 각 분할 단계에서 정확히 이등분 될 때
▷ 교환 및 비교 회수가 매우 적음 : 단순하고 매우 빠른 속도로 수행
▷ 안정성은 없음
▷ 난수 배열 및 반쯤 정렬된 배열 자료에 대해서는 성능이 우수
▷ 피봇이 중간 값을 갖도록 해야 수행속도가 좋아짐