[Algorithm] 퀵 정렬(Quick Sort)

1. 퀵 정렬(Quick Sort)이 나온 배경

---

배열 안에 있는 원소들을 정렬하기 위한 방법으로 "선택 정렬, 삽입 정렬, 버블 정렬" 이라는 방법을 사용했다면

이는 시간 복잡도가 O(n^2)인 알고리즘으로,

즉 데이터가 커지면 커질 수록 계산 시간이 급격하게 증가하는 치명적인 단점을 보유하고 있다.

 

이러한 문제를 해결하기 위해,

도입된 정렬 알고리즘이 분할 정복 전략(Divide n Conquer Strategy)을 이용한 알고리즘이고, 대표적으로 퀵 정렬이 있다.

 

2. 퀵 정렬(Quick Sort)에 대한 대략적인 개념

---

앞서 말했다시피, 퀵 정렬은 분할 정복 전략을 이용해서 정렬을 수행하는데,

 

1) 여기서, 분할 정복 전략은 무엇일까?

특정 문제(main problem)를 해결하기 위해서 그 문제와 관련된 여러개 작은 문제(sub problems)로 나누고,
이러한 작은 문제에 대한 결과 값을 종합해서(Combination), 특정 문제를 해결하는 전략이라고 한다.

 

2) 그렇다면 이러한 전략을 어떻게 이용해서 퀵 정렬 알고리즘이 수행될까?

간단하게 애기하자면 아래와 같다,

Array(배열)에서 특정한 값(Pivot)을 잡고 그 값을 기준으로 작은 배열, 큰 배열로 분할하자

 

전체 배열에 있는 모든 원소들을 모두 비교하는 과정은 어려운 문제이니,

-> 전체 배열의 특정 값(Pivot)을 기준으로 그것 보다 작은 것들의 집합, 큰 것들의 집합으로, 두 집합으로 나누면서

-> 비교 과정을 수행하자는 것이다.

3. 퀵 정렬(Quick Sort)의 전체적인 과정

---

 

그렇다면 퀵정렬에 대해 간단히 알아봤으니, 지금부터는 퀵 정렬이 수행되어지는 과정에 차근차근 알아보자.

 

 

 

4. 전체 코드

---

#include <iostream>

using namespace std;

void showArray(int* arr) {
	
	for (int i = 0; i < 10; i++) { cout << arr[i] << " "; }
	cout << endl;

}

int makePartition(int* arr, int start, int end) {
	
	int pivotIdx = arr[start];

	int count = 0;
	for (int i = start+1; i <= end; i++) {
		if (arr[i] < pivotIdx) {
			count++;
		}
	}
	pivotIdx = start + count;
	swap(arr[start], arr[pivotIdx]);

	int i = start, j = end;
	while (i < pivotIdx && j > pivotIdx) {
		while (arr[i] <= arr[pivotIdx]) { i++; } // Left subArray Traversal
		while (arr[j]  > arr[pivotIdx]) { j--; } // Right subArray Traversal
		
		if (i < pivotIdx && j > pivotIdx) {
			swap(arr[i], arr[j]);
		}
	}

	return pivotIdx;

}
void quickSort(int *arr, int start, int end){
	
	if (start >= end) {
		// if the length of Array is at most 1, exit the function
		return;
	}

	int pivotIdx = makePartition(arr, start, end);

	quickSort(arr, start, pivotIdx - 1);
	quickSort(arr, pivotIdx + 1, end);

}

int main() {

	int arr[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 9 };
	const int length = 10;

	quickSort(arr, 0, length - 1);
	showArray(arr);

	return 0;

}