퀵 정렬(Quick Sort)

• 퀵 정렬(Quick Sort)

기준이 되는 피벗(pivot)을 기준으로 배열을 두 그룹으로 나눈 후 피벗을 기준으로 더 작은 값은 왼쪽으로, 큰 값은 오른쪽을 옮김.

 

1. 한 배열의 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때

2. a[pl] >= x인 pl과 a[pr] <= x인 pr을 찾아 두 값을 교환 (x = a[pivot])

3. pl과 pr이 교차하게 되면 나눠진 두 그룹에 대하여 각각 위의 과정을 반복

 

void quick(int a[], int left, int right) {
	int pl = left;
	int pr = right;
	int x = a[(pl + pr) / 2];
	do {
		while (a[pl] < x) pl++;
		while (a[pr] > x) pr--;
		if (pl <= pr) {
			swap(a[pl], a[pr]);
			pl++;
			pr--;
		}
	} while (pl <= pr);
	if (left < pr) quick(a, left, pr);
	if (pl < right) quick(a, pl, right);
}

 

시간복잡도:O(n log n) - best, avg (worst는 O(n^2))

---

<stdlib.h>의 qsort() 함수 이용

int int_cmp(const int *a, const int* b){
    if(*a < *b) return -1;
    else if(*a > *b) return 1;
    else return 0;
}

...

qsort(배열, 배열개수, sizeof(요소자료형), int_cmp);

 

구조체의 문자열을 기준으로 배열하고자 할 때 compare 함수 예시

int npcmp (const Person* x const Person* y){
    return strcmp(x->name, y->name);
}