Quick Sort(퀵 정렬)

퀵 정렬은 분할 정복 알고리즘(문제를 나눌 수 없는 작은 단위까지 나누고 다시 각각을 합치면서 답을 얻는 알고리즘)이다.
pivot값이라는 기준값을 가지게 되며, pivot값은 대개 맨 앞에 있는 원소를 기준으로 하게 된다.

퀵정렬은 분할정복 알고리즘으로써 최선의 알고리즘 속도를 가진다면, O(N * logN)의 속도를 가지지만 최악의 경우 O(N^2)의 속도를 가진다.

Quick Sort Code

#include<iostream>

void QuickSort(int* data, int start, int end)
{
	if(start >= end)
	{
		return;
	}
	
	int key = start;
	int i = start + 1, j = end, temp;
	
	while(i <= j)
	{
		while( i <= end && data[i] <= data[key])
		{
			i++;
		}
		while( j > start && data[j] >= data[key])
		{
			j--;
		}
		if( i > j)
		{
			temp = data[j];
			data[j] = data[key];
			data[key] = 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 data[] = {5, 8, 2, 7, 4, 1, 9, 6, 3};
	int number = 9;
	
	QuickSort(data, 0, number - 1);
	
	for(int i = 0 ; i < 9 ; i++)
		std::cout << data[i] << " ";
	return 0;
}

이미지 출처
자료 출처