[Sorting 01] Quick Sort의 개념 및 구현

들어가며

---

대학을 다니면서 알고리즘 과목을 수강하기도 했고 알고리즘 스터디도 했다.

혼자 온라인 저지 사이트에 들어가 쉬운 문제들을 빠르게 풀며, 또는 어려운 문제를 며칠씩 고민해가며 풀기도 했다.

 

그런데 놀랍게도,

내 머릿 속에 남아있는 알고리즘 지식은 거의 없다.

'누군가 지금 당장 다익스트라를 구현해보시오.' 한다면 나는 분명 다익스트라를 익히 들어서 그 이름은 알고 있으나,

어떤 메커니즘을 가진 알고리즘인지 바로 떠올리지 못할 것이다.

 

이는 내 공부가 체계적이지 않았기 때문이라는 결론에 도달했다.

한 알고리즘을 배우고 이에 대한 다수의 문제를 풀어서 내껄로 만들었던 것이 아니라,

그때그때 필요한 알고리즘들을 찾아보고 그걸 써왔기 때문이다.

 

그래도 나름 열심히 배웠던 지식들이, 그저 머리를 스쳐지나가는 것이 아쉬워서

이 카테고리 블로그 포스팅을 통해 알고리즘들을 정리해보고자 한다.

 

오늘은 첫 번째로 Quick sort에 대해 알아본다.

 

개념 및 특징

---

• Quick Sort는 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다.
• 최악 시간 복잡도: O(N²)
• 최선 시간 복잡도: O(NlogN)
• 평균 시간 복잡도: O(NlogN)
• 최악인 경우는 미리 정렬되어있는 경우로, 오름차순 혹은 내림차순으로 이미 정렬이 되어있고 pivot으로 맨 앞 또는 맨 뒤의 수를 선택하는 경우이다.

알고리즘

---

 

Quick Sort는 분할 정복(divide and conquer)를 통해 정렬한다. 정렬 방법은 다음과 같다.

1) 리스트 가운데서 하나의 원소를 고른다. 이를 pivot이라고 부른다.

2) pivot을 기준으로 정렬하는데, pivot 보다 값이 작은 원소들은 pivot보다 앞에 오고 pivot 보다 값이 크거나 같은 원소들은 pivot보다 뒤에 오도록 정렬한다. 이렇게 pivot을 기준으로 리스트가 둘로 나눠지는 것을 division이라고 한다.

3) 나눠진 두 개의 리스트에 대해 재귀적으로 1~2의 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복한다.  

 

소스코드(C++)

---

#include <iostream>
#include <vector>
#include <iterator>

using namespace std;

vector<int>::iterator sorting(vector<int>::iterator low, vector<int>::iterator high)
{
	int pivot = *low;
	vector<int>::iterator lit = low+1;
	vector<int>::iterator hit = high-1;
	while(lit<=hit) {
		for(;lit<=hit && !(*lit >= pivot);++lit)
			;
		for(;hit>=lit && !(*hit < pivot);--hit)
			;
		if(lit<=hit) {
			int tmp = *lit;
			*lit = *hit;
			*hit = tmp;
			lit++;
			hit--;
		}		
	}
	int tmp = *hit;
	*hit = *low;
	*low = tmp;
	
	return hit;
}

void quickSort(vector<int>& vc, vector<int>::iterator low, vector<int>::iterator high)
{
	if(low==high)
		return;
	
	vector<int>::iterator it = sorting(low, high);
	quickSort(vc,low,it);
	quickSort(vc,it+1,high);
}

int main(void)
{
	int arr[] = {13, 7, 22, 5, 1, 3, 2, 11};
	vector<int> vc(arr,arr+sizeof(arr)/sizeof(arr[0]));
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl; 
	
	quickSort(vc,vc.begin(),vc.end());
	
	copy(vc.begin(), vc.end(), ostream_iterator<int>(cout," "));
	cout << endl;	
	return 0;
}

관련 문제

---

• 백준 2751번: 수 정렬하기 2(https://www.acmicpc.net/problem/2751)
• 백준 11004번: K번째 수(https://www.acmicpc.net/problem/11004)