퀵 정렬(Quick Sort)

 퀵 정렬(Quick Sort)은 분할 정복 알고리즘의 일종으로, 배열을 임의의 기준으로 두 부분으로 나눈 후 각각을 재귀적으로 정렬하는 방식입니다. 평균 시간 복잡도는 O(nlog⁡n)이며, 최악의 경우 O(n ² )이 될 수 있습니다. 일반적으로 빠른 수행 속도로 널리 사용되는 정렬입니다.

---

「퀵 정렬의 동작 과정」

---

1. 분할 과정 (Divide)

 퀵 정렬의 첫번째 단계에서는 "피벗(pivot)"을 정해 이를 통해 구간을 나누는 과정입니. 피벗은 일반적으로 배열의 첫 번째 원소, 마지막 원소, 또는 중앙값을 선택합니다. 피벗을 정한뒤, 배열의 원소들을 피벗을 기준으로 두 부분으로 나눕니다. 피벗보다 작은 원소들은 피벗의 왼쪽에, 피벗보다 큰 원소들은 피벗의 오른쪽에 위치하도록 합니다.

 

-처음 주어진 배열

[38, 27, 43, 3, 9, 82, 10]

-피벗을 38로해 나눈다.

[ 27,3,9,10], [38], [43, 82]

---

2. 정복 과정 (Conquer)

정복(Conquer) 단계에서는 피벗을 기준으로 나뉜 두 부분 배열에 대해 재귀적으로 같은 과정을 적용합니다. 이 과정을 통해 각 부분 배열이 더 작은 부분 배열로 계속 나뉘어 정렬됩니다.

 

-왼쪽배열의 피벗을 27로 한다.

[ 3,9,10], [27], [38], [43, 82]

-왼쪽 배열의 피벗을 3으로 한다.

[3], [9, 10], [27], [38], [43, 82]

-[9, 10]배열의 피벗을 9로한다.

[3], [9], [10], [27], [43, 82]

-맨 오른쪽 배열의 피벗을 43으로한다.

[3], [9], [10], [27], [53], [82]

---

3. 결합 과정 (Combine)

 실제로는 퀵 정렬은 부분 배열을 결합(Combine)하는 별도의 과정이 필요하지 않습니다. 모든 부분 배열이 정렬된 후, 피벗들이 이미 정렬된 상태로 각 부분 배열의 경계에 위치하여 전체 배열이 정렬된 상태가 됩니다.

-정렬된 배열

[3, 9, 10, 27, 38, 43, 82]

---

퀵 정렬을 공부했으니 다음 문제를 풀어보자

https://jungol.co.kr/problem/3518

 

《소스코드》

이 소스는 피벗을 가장 뒤 원소로 잡았다.

#include <stdio.h> 
#include <algorithm>

using namespace std;

int n, arr[1000010];

void quick_sort(int l, int h) {
	int i, j;
	if (l >= h) return;
	i = l - 1;
	int pivot = arr[h];
	for (j = l; j < h; j++) {
		if (arr[j] < pivot) {
			swap(arr[++i], arr[j]);
		}
	}
	swap(arr[++i], arr[h]);
	quick_sort(l, i - 1);
	quick_sort(i + 1, h);
}

int main()
{
	int i, j;
	int l, h;
	scanf("%d", &n);
	for (i = 0; i < n; i++) scanf("%d", &arr[i]);
	l = 0, h = n - 1;
	quick_sort(0, n - 1);
	for (i = 0; i < n; i++) printf("%d ", arr[i]);
	return 0;
}