(정렬) 퀵정렬

pseudo code

QuickSort(A, left, right)
입력: 배열 A[left]~A[right]
출력: 정렬된 배열 A[left]~A[right]
if(left < right){
	피봇을 A[left]~A[right] 중에서 선택하고, 피봇을 A[left]와 자리를 바꾼 후, 피봇과 배열의 각 
    원소를 비교하여 피봇보다 작은 숫자들은 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자들은 
    A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다.
    QuickSort(A, left,p-1);
    QuickSort(A,p+1,right);
}

 

c 코드

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

void swap(int* n1, int* n2) {
	int tmp = *n1;
	*n1 = *n2;
	*n2 = tmp;
}

void QuickSort(int* A, int left, int right) {
	if (left < right) {
		int p, l = left; int r = right;
		int pivot = A[(left+right)/2];
		while (l < r) {
			while (A[l] < pivot) { l+=1; }
			while (A[r] > pivot) { r-=1;}
			if (A[l] == A[r]) {
				r--; l++;
			}
			if (l >= r) {
				break;
			}
			swap(&A[r], &A[l]);

		}
		for (p = left; p < right && A[p] != pivot; p++);
		QuickSort(A, left, p - 1);
		QuickSort(A, p + 1, right);
	}
}

실행 시간 

8개 : 0.000

10,000개 : 0.003

100,000개 : 0.162

600,000개 : 5.186

1,000,000개 : 14.549