Quick Sort (퀵정렬)

Quick Sort(퀵정렬)

 

알고리즘

 

연속적인 분할에 의한 정렬. 처음 하나의 축을 정해서 이 축의 값보다 작은 값은 왼쪽에

큰 값은 오른쪽으로 위치시킨다. 왼쪽과 오른쪽의 수 들은 다시 각각의 축으로 나누어져

축값이 1이 될 때까지 정렬한다

 

특징

 

안정성 없음

 

O(NlogN) : 최선의 경우 log₂N (축값이 정확히 가운데를 가질 경우)

O(N^2) : 최악의 경우

 

가장 많이 사용되는 정렬법으로 1960년 C.A.R. Hoare에 의해 고안되었다.

 

Code(코드)

 

재귀함수를 사용한다.

 

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define SIZE 20
#define SWAP(x,y,t) ( (t)=(x), (x)=(y), (y)=(t) )
 
void QuickSort(int left, int right);
 
int array[SIZE];
 
int main(void){
	int i;
	srand((unsigned int)time(NULL));
 
	for ( i = 0; i < SIZE; i++ )
		array[i] = rand() % (SIZE*10) + 1;
 
	printf("array for sorting : \n");
 
	for ( i = 0; i < SIZE; i++ )
		printf("%4d", array[i]);
 
 
	printf("\nProcessing : \n");
 
	QuickSort(-1, SIZE-1);
 
	printf("Soredted array : \n");
 
	for ( i = 0; i < SIZE; i++ )
		printf("%4d", array[i]);
 
	printf("\n");
 
	return 0;
}
 
void QuickSort(int left, int right){
	int m, p, t;
	int i, j;
 
	for ( i = 0; i < SIZE; i++ )
		printf("%4d", array[i]);
 
	printf("\n");
 
	if ( left < right ){
		p = array[right];           
		
		for(i=left-1, j=right; ; ){
			while ( array[++i] < p );   
			while ( array[--j] > p );
 
			if ( i > j )          
				break;
 
			SWAP(array[i], array[j], t);
			}
 
		array[right] = array[i];
		array[i] = p;
 
		QuickSort(left, j);    
		QuickSort(i+1, right);     
	}
}