퀵 정렬( Quick Sort )

가장 널리 사용되는 정렬 방법중 하나.

연속적인 분할을 해서 정렬하는 방법으로 자료 값 중 Pivot값을 하나 정하여

왼쪽은 작은 값, 오른쪽은 큰값을 배치한다.

나누어진 왼쪽,오른쪽을 다시 분할하여 위 방법으로 정렬하는 방법

재귀의 깊이가 log2N이 되어 가장 빠른 성능을 나타낸다

난수에 대한 정렬에서 빠르다

하지만 정렬이 되거나 역순으로 배열된 자료에 대해선 느리다. 추가 메모리가 필요하다.

1. 배열에서 Pivot값을 하난 정한다.(보통 맨 마지막 값)

2. 배열의 왼쪽과 오른쪽에서 각각 탐색을 시작한다.

3. 왼쪽에서 Pivot보다 큰값, 오른쪽에서 Pivot보다 작은값이 나오면 둘을 교환한다.

4. 왼쪽에서 탐색하던 것이 오른쪽 보다 커지면 탐색을 종료한다.

5. Pivot값을 왼쪽과 오른쪽 탐색의 교차지점과 교환한다.

6. Pivot에서 왼쪽, 오른쪽 부분을 위와 같은 방법으로 다시 정렬 한다

7. 각 정렬되는 부분의 길이가 1보다 작거나같으면 정렬을 종료한다.

     left    right       pivot

3 5 2 1 4     3        1            4

3 5 2 1 4    5        1                4        : left롸 right 교환

3 1 2 5 4        1        5            4

3 1 2 5 4        2        5            4

3 1 2 5 4        5           5        4

3 1 2 4 5                                3      : pivot값을 중심으로 변경

3 1 2 4 5         3        1            2

1 3 2 4 5        1        3               2    : left와 right 교환

1 3 2 4 5        3        3            2

1 2 3 4 5           1                    2       : pivot값을 중감으로 변경

#include <stdio.h>

void Print_Arr( int arr[], int size )

{

for( int i = 0 ; i < size ; i++ )

{

printf("%d", arr[i] );

if( i < size ) printf(" ");

else printf("\n");

}

printf("\n");

}

void Quick_Sort( int arr[], int size )

{

int Pivot, temp;

int i, j;

if( size > 1 )

{

Pivot = arr[size-1];

i = -1;

j = size - 1;

while( 1 )

{

while( arr[++i] < Pivot );

while( arr[--j] > Pivot );

if( i >= j ) break;

temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}

temp = arr[i];

arr[i] = arr[size-1];

arr[size-1] = temp;

Quick_Sort( arr, i );

Quick_Sort( arr+i+1, size-i-1 );

}

}

void main()

{

int arr[20] = {5,1,4,0,100,.................};

Print_Arr( arr, 20 );

Quick_Sort( arr, 20 );

Print_Arr( arr, 20 );

}