퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick-Sort)

- 퀵 정렬의 내부 루프는 대부분 컴퓨터의 아키텍처에서 효율적으로 작동하도록 설계되어 있다.

( 메모리 참조가 지역화되어 있기 때문에 CPU 캐시의 히트율이 높기 때문 )

- 일반적으로 퀵 정렬은 평균적으로 O(n log n)번의 비교를 수행한다. ( 최악의 경우 O(n²) )

- 정렬을 위해 작은 공간( O(log n) )의 메모리를 필요로 한다.

2. 동작 원리

1. 리스트의 중간 원소를 피벗으로 지정한다.

2. 피벗을 기준으로, 앞에는 피벗보다 값이 작은 원소들을 배치하고

 뒤에는 피벗보다 값이 큰 원소들을 배치한다.

 ( 이렇게 리스트를 나누는 것을 "분할(partition)"이라고 한다. )

3. 분할된 두 개의 리스트에 대해 재귀적으로 이 과정을 반복한다.

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

#define MAX  10 // size of array

void display_elements( int *, int);
void quick_sort( int *, int, int);

int main( void)
{
 int arry[MAX]  = { 0,};
 int count   = 0;
 int size   = 0;

 srand( time(NULL)); // used to init random

 size  = sizeof(arry)/4;

 // init elements of array with random numbers
 for( count = 0 ; count < size ; count ++)
 {
  arry[count]  = rand()%(MAX*10);
 }

 // display elements of array
 printf("Before sorting : ");
 display_elements( arry, size);

 // call Insertion-Sort
 quick_sort( arry, 0, size-1);

 // output result
 printf("\n After sorting : ");
 display_elements( arry, size);

 return 0;
}

void display_elements( int *ar, int s)
{
 int count  = 0;

 for( count = 0 ; count < s ; count ++)
 {
  printf("%4d", ar[count]);
 }
}

void quick_sort( int *ar, int start, int end)
{
 int pivot = ar[(start + end) / 2]; // set a pivot to devide partition
 int l  = start;
 int r  = end;
 int temp = 0;

 /*
  sort the array with the pivot.
  if a number that positioned left is bigger than the pivot,
  it is swapped with a number that positioned right and smaller than the pivot.
 */
 while( l <= r)
 {
  // find a number bigger than the pivot
  while( ar[l] < pivot)
  {
   l ++;
  }
  // find a number smaller than the pivot
  while( ar[r] > pivot)
  {
   r --;
  }

  if( l <= r)
  {
   temp = ar[r];
   ar[r--] = ar[l];
   ar[l++] = temp;
  }
 };

 // recursion to sort other partions
 if( r > start)
 {
  quick_sort( ar, start, r);
 }
 if( l < end)
 {
  quick_sort( ar, l, end);
 }
}