[알고리즘] Quick sort

종류

분할-정복 알고리즘입니다. 분할-정복 알고리즘은 재귀적으로 자신을 호출하면서 연산 단위를 조금씩 줄여나가는 방법입니다. 재귀 호출이 한 번 진행될 때마다 최소 하나의 원소는 위치가 정해지기 때문에 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있습니다. 

 

장점

재귀호출의 과정에서 임시 메모리를 쓰는 것은 성능 저하를 가져오기 때문에(리턴값을 사용하지 않음) 배열 내부에서 분할 작업을 구현하는 편이 좋습니다. 퀵 정렬은 메모리 참조가 지역화되어 있기 때문에(캐시의 공간 지역성) 캐시 히트률이 높습니다. 이런 이유로 일반적인 경우 퀵 정렬은 다른 O(nlogn) 알고리즘보다 빠르게 작동합니다.

 

기본 흐름

피벗을 기준으로 왼쪽에는 피벗보다 작은 원소를, 오른쪽에는 피벗보다 큰 원소들을 위치합니다. 개념적으로 왼쪽에서 피벗보다 큰 수를 찾아 스왑하거나 오른쪽에서 피벗보다 작은 수를 찾아 스왑하는 방식이 반복됩니다. 코드에서는 가장 오른쪽 원소를 피벗으로 정하고 해당 값을 기준으로 원소 위치를 변경합니다. swap을 하는 조건이 arr[j]의 값이 피벗보다 작은 경우이기 때문에 빈복문을 탈출하면 i 인덱스는 피벗보다 큰 원소 중 가장 작은 원소의 위치를 가리키게 되어 있습니다. 

 

코드

// quick_sort.h
#pragma once
class QuickSort
{
public:
	void sort(int arr[], int low, int high);
	void swap(int& a, int& b);
};

// quick_sort.cpp
#include "quick_sort.h"

void QuickSort::sort(int arr[], int low, int high)
{
	if (low >= high) return;
	int i = low, j = low;
	int& pivot = arr[high];
	for (; j < high; ++j)
		if (arr[j] < pivot)
			swap(arr[i++], arr[j]);
	swap(arr[i], pivot);

	sort(arr, low, i - 1);
	sort(arr, i + 1, high);
}

void QuickSort::swap(int& a, int& b)
{
	int temp = a;
	a = b;
	b = temp;
}

// main.cpp
#include "quick_sort.h"
#include <iostream>

int main()
{
	QuickSort qs;
	int arr[] = { 11, 5, 10, 7, 9, 12, 15, 13, 8, 6, 7, 4 };
	int high = _countof(arr) - 1;
	qs.sort(arr, 0, high);
	for (int n : arr)
		std::cout << n << " ";
}