02. 퀵 정렬

퀵 정렬의 정의

• 피벗을 기준으로 큰 값과 작은 값을 서로 교체하는 정렬 기법
• 교체하는데에 N번, 교체 이후 원소가 반으로 나누어져 전체 원소를 나누는데 평균 log N번 소요
  --> O(NlogN)의 시간 복잡도

퀵 정렬의 과정

원소를 절반씩 나눌 때 log N의 시간 복잡도가 나오는 대표적인 예시는 완전 이진 트리

퀵 정렬의 구현

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 1000

int a[SIZE];

// swap 함수
int swap(int* a, int* b) {
	int temp = *a;
	*a = *b;
	*b = temp;
}

// quick 정렬
void quickSort(int start, int end) {
	if (start >= end) return;
	int key = start, i = start + 1, j = end, temp; // key가 피벗

	while (i <= j) {
		while (i <= end && a[i] <= a[key]) i++;  // 피벗보다 큰값을 찾음
		while (j > start&& a[j] >= a[key]) j--;  // 피벗보다 작은값을 찾음

		if (i > j) swap(&a[key], &a[j]);  // 위치가 어긋나지 않았다면 교환
		else swap(&a[i], &a[j]);   // 위치가 어긋났다면 피벗과 작은값 교환
	}
	// 분할하여 각각 퀵 정렬 집행
	quickSort(start, j - 1); 
	quickSort(j + 1, end);
}

// main 함수
int main(void) {
	int n;
	scanf("%d", &n);
	for (int i = 0;i < n;i++) scanf("%d", &a[i]);
	quickSort(0, n - 1);
	for (int i = 0; i < n;i++) printf("%d ", a[i]);
	system("pause");
	return 0;
}

퀵 정렬의 단점

• 편향된 분할이 발생할 때 연산량이 O(N^2)
• 실제 정렬함에 있어 퀵 정렬을 직접 구현하지 않음

C++ Algorithm 라이브러리의 sort() 함수는 퀵정렬 기반의 O(N logN)을 보장