[C++] 퀵 정렬 (Quick sort) 개념 및 구현

특징

1. 분할 정복 알고리즘

2. 동일한 원소 존재시, 원래의 순서를 보존하지 않는 불안정 정렬

3. 일반적으로 최고, 평균 시간 복잡도O(N * logN), 최악 O(N^2)

4. 추가 버퍼가 필요하지 않으므로 공간 복잡도 O(1)

 

 

알고리즘

 

1. 버퍼의 요소 중 하나를 피벗(pivot)으로 지정

    보통 맨 왼쪽, 중앙, 맨 오른쪽으로 지정하고, 본 포스팅은 피벗을 맨 왼쪽으로 함

2. 피벗보다 작은 값을 피벗의 왼쪽으로 이동, 피벗보다 큰 값을 피벗의 오른쪽으로 이동

3. 피벗을 기준으로 왼쪽 버퍼와 오른쪽 버퍼를 나누어 각 재귀 함수 호출

 

구현에서 중요한 점은 퀵 정렬은 추가 버퍼를 사용하지 않는 In-place sort라는 것이다.

따라서 2번 과정에서 새로운 버퍼를 이용하지 않고, 한 버퍼에서 swap을 하며 진행한다.

 

 

구현 및 상세 설명

void sort(std::vector<int>& buf)
{
	recursion(buf, 0, buf.size()-1);
}

 

먼저 sort()에서는 재귀 함수를 처음으로 호출한다.

 

static void swap(int& first, int& second)
{
	int temp = first;
	first = second;
	second = temp;
}

static void recursion(std::vector<int>& buf, int start, int end)
{
	if (start >= end)
		return;

	int& pivot = buf[start];
	int left = start + 1;
	int right = end;

	while (true)
	{
		while (left <= right && buf[left] <= pivot)
			++left;
		while (left <= right && buf[right] > pivot)
			--right;
			
		if (left > right)
			break;
		swap(buf[left], buf[right]);
	}

	swap(pivot, buf[right]);
	recursion(buf, start, right - 1);
	recursion(buf, right + 1, end);
}

 

호출한 재귀함수는 입력 버퍼와 start 인덱스, end 인덱스를 인자로 받는다.

그리고 피벗을 기준으로 요소들을 나누기 위해 중요한 과정을 진행한다.

 

우선 피벗 제외 버퍼의 맨 왼쪽 index를 left, 맨 오른쪽 index를 right로 지정한다.

 

 

left가 가리키는 요소가 피벗보다 클 때까지 left를 증가시킨다.

이후 right가 가리키는 요소가 피벗보다 작거나 같을 때까지 right를 감소시킨다.

 

이 때, left가 right를 지나쳤다면 반복문을 종료한다.

그렇지 않다면, left 값과 right 값을 바꾸고 반복문을 재개한다.

 

 

반복문이 종료되는 경우는 다음 두 가지다.

1. left 차례에 right를 지나쳤다면, right가 가리키고 있는 값은 피벗보다 작다는 뜻이고

2. right 차례에 left를 지나쳤다면, left가 지나쳐온 피벗보다 작은 값을 right가 가리키게 된다.

 

결국 right가 가리키는 값이 항상 피벗보다 작거나 같게 되므로 피벗과 right 값을 바꾼다면
해당 버퍼는 피벗의 왼쪽에는 피벗보다 작은 값이, 피벗의 오른쪽에는 피벗보다 큰 값이 위치하게 된다.

 

이제 피벗을 기준으로 양 옆 버퍼를 분할하여 각 재귀함수를 호출한다.

 

 

최악의 경우

피벗을 왼쪽에 두었을 때,

오름차순 혹은 내림차순으로 정렬되어있는 입력 버퍼의 경우 O(N^2)의 시간복잡도를 보인다.

 

 

 

테스트

#include <vector>
#include <iostream>
#include <cstdlib>
#include "QuickSort.hpp"

static void sortChecker(std::vector<int>& buf)
{
	for (int i=0; i<(int)buf.size()-1; ++i)
	{
		if (buf[i] > buf[i+1])
		{
			std::cout << "\e[31mX\e[0m ";
			return;
		}
	}
	std::cout << "\e[32mV\e[0m ";
}

int main(int ac, char** av)
{
	if (ac < 2)
	{
		std::cout << "<Usage> : ./a.out 5 2 4 1 3\n";
		return 1;
	}

	std::vector<int> buf;
	buf.reserve(ac);

	for (int i=1; i<ac; ++i)
		buf.push_back(atoi(av[i]));

	quick::sort(buf);
	
	sortChecker(buf);
	return 0;
}

 

#!/bin/bash

# Linux
echo -n "1. Positive test : "
$1 `seq 0 0 | shuf | tr "\n" " "`
$1 `seq 0 2 | shuf | tr "\n" " "`
$1 `seq 1 100 | shuf | tr "\n" " "`
$1 `seq 1 100000 | shuf | tr "\n" " "`
$1 `seq 2147480000 2147483647 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" " "`
done
echo ""

echo -n "2. Negative test : "
$1 `seq -1 -1 | shuf | tr "\n" " "`
$1 `seq -2 0 | shuf | tr "\n" " "`
$1 `seq -100 -1 | shuf | tr "\n" " "`
$1 `seq -99999 -1 | shuf | tr "\n" " "`
$1 `seq -2147483648 -2147473648 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" "_" | sed 's/_/ -/g'`
done
echo ""

echo -n "3. Integer test : "
$1 `seq -1 1 | shuf | tr "\n" " "`
$1 `seq -3 2 | shuf | tr "\n" " "`
$1 `seq -100 100 | shuf | tr "\n" " "`
$1 `seq -33121 32451 | shuf | tr "\n" " "`
$1 `seq -3 123123 | shuf | tr "\n" " "`
$1 `seq -112312 6 | shuf | tr "\n" " "`
for _ in {1..50}; do
	$1 `shuf -i 1-10000000 -n 1000 | tr "\n" " "` `shuf -i 1-10000000 -n 1000 | tr "\n" "_" | sed 's/_/ -/g'`
done
echo ""

결과

 

 

전체 코드

https://github.com/SikPang/Algorithms/tree/main/QuickSort

 

 

참고 자료

https://www.youtube.com/watch?v=59fZkZO0Bo4

 

개인 공부용 포스팅인 점을 참고하시고, 잘못된 부분이 있다면 댓글로 남겨주시면 감사드리겠습니다.