[알고리즘] 퀵 정렬(Quick sort)

퀵 정렬(Quick sort)

 

quick 정렬의 source code이다. C에서 기본으로 제공하는 qsort는 아래와 같은 원리도 동작한다.

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

void swap(int* a, int* b)
{
	int temp = *a;
    *a = *b;
    *b = temp;
}

int quickSort(int* arr, int left, int right)
{
	int L = left, R = right;
    int pivot = arr[(left + right)/2];
    
    do { 
    	while( arr[L] < pivot )
        	L++; 
            
		while( arr[R] > pivot )
    		R--;
            
		if( L <= R )
		{
			swap(&arr[L], &arr[R]);
			L++;
			R--;
		} 
	} while( L <= R );
    
    if( left < R )
    	quickSort(arr, left, R);

	if( L < right )
    	quickSort(arr, L, right);
}

int main() 
{
	int num =0, i = 0, j = 0, input = 0;
    int *arr = NULL;
    
    scanf("%d", &num);
    arr = (int*)calloc(num, sizeof(int));
    for(i=0; i<num; i++)
    {
    	scanf("%d", &input);
        arr[i] = input;
	}
    
    quickSort(arr, 0, num-1);
    for(i=0; i<num; i++)
    {
    	printf("%d\n", arr[i]);
	}

	free(arr);
    arr = NULL;
    return 0;
} 

 

c에서 제공하는 qsort를 이용하여 정렬한다.

첫번째는 sort 할 포인터, 두번째는 크기, 세번째는 포인터 형(간격), 네번째는 compare 함수.

compare 함수에 구현된 부분은 오름차순 정렬을 기본으로 하였으며, 내림차순으로 정렬하기 위해서는 return value가 반대로 되도록 해준다.

#include <stdio.h> #include <stdlib.h> int compare(const void* a, const void* b) { if( *(int*)a > *(int*)b ) return 1; else if( *(int*)a < *(int*)b ) return -1; else return 0; } int main() { int num =0; int *arr = NULL; scanf("%d", &num); arr = (int*)calloc(num, sizeof(int*)); for(int i=0; i<num; i++) scanf("%d", &arr[i]); qsort(arr, num, sizeof(int), compare); for(int i=0; i<num; i++) printf("%d ", arr[i]); free(arr); return 0; }