티스토리 뷰

Computer/Algorithms

Quick Sort (퀵정렬)

jamezc 2015. 6. 4. 17:38

Quick Sort(퀵정렬)

 

알고리즘

 

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

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

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

 

특징

 

안정성 없음

 

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

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);
}
}


댓글

파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음



Total
Today
Yesterday
최근에 달린 댓글