2-3) [C] 퀵정렬(Quick Sort)

1) 퀵 정렬이란?

기준이 되는 수(pivot)를 수열 안에서 임의로 선택한 후 'pivot 보다 작은 수'와 'pivot 이상인 수'의 두 그룹으로 나누고 이것을 배치

2) 퀵 정렬의 시간복잡도

각 층에서 각 숫자는 pivot과 1회만 비교되므로 한 층의 계산 시간은 O(n)이 되고, 전체 계산 시간은  O(n log n)이다.

3) 퀵 정렬 구현

#include <stdio.h>

void quickSort(int* data, int start, int end) {
	if (start >= end) {
		return;
	}
	int pivot = start;
	int i = start + 1;
	int j = end;
	int temp;

	while (i <= j) { // 엇갈릴 때까지
		while (i <= end && data[i] <= data[pivot]) // 피벗 보다 큰 값을 만날 때까지
			i++;
		while (j > start && data[j] >= data[pivot]) // 피벗 보다 작은 값을 만날 때까지
			j--;
		if (i > j) { // 엇갈리면 피벗과 교체
			temp = data[j];
			data[j] = data[pivot];
			data[pivot] = temp;
		}
		else { // 엇갈리지 않으면
			temp = data[i];
			data[i] = data[j];
			data[j] = temp;
		}
	}
	quickSort(data, start, j - 1);
	quickSort(data, j + 1, end);
}

int main() {
	int arr[10] = { 4, 9, 1, 6, 11, 10, 3, 15, 2, 13 };
	quickSort(arr, 0, 9);
	for (int i = 0; i < 10; i++)
		printf("%d ", arr[i]);
        
	return 0;
}

결과화면

1 2 3 4 6 9 10 11 13 15