퀵 소트(Quick Sort) STL 없이 구현

알고리즘을 풀 때 주로 stl에서 제공하는 sort 메서드를 사용하기 때문에 퀵 소트를 구현하는 방법을 잊어버리는 경우가 많습니다.

실제 면접에서 퀵 소트를 구현하라는 경우가 적지 않으니 퀵 소트를 구현해보겠습니다.

	#include <iostream>
	using namespace std;
	// 범위는 [begin, end)
	void quickSort(int *arr, int begin, int end)
	{
	// 재귀 종료 조건
	if (end - begin <= 1)
	return;
	int pivot = arr[begin]; // 기준
	int left = begin + 1;
	int right = end - 1;
	while (1)
	{
	while (left <= right && arr[left] <= pivot)
	left++;
	while (left <= right && arr[right] >= pivot)
	right--;
	if (left > right)
	break;
	swap(arr[left], arr[right]);
	}
	swap(pivot, arr[right]);
	// 반으로 쪼개어 정렬
	quickSort(arr, begin, right);
	quickSort(arr, right + 1, end);
	}

view raw c++ hosted with ❤ by GitHub