분할 통치) 퀵 정렬 (Quick Sort)

귀찮아서 미루고 미루다, 이제야 작성하네요

이걸로 정렬은 끝나고 다른 알고리즘들을 다루어야겠습니다 ㅎㅎ

정렬 알고리즘 전체 코드는 코드 게시판가면 있어요 (c++로 작성했음)

§ 퀵 정렬 (Quick Sort)

퀵 정렬 또한 분할통치법을 이용한 알고리즘입니다.

퀵 정렬의 핵심은 피벗(Pivot) 입니다.

여기서 피벗이란?

기준점입니다.

무조건 이걸 피벗으로 써야한다! 하는 기준은 없고, 각자 편한대로 정해주시면 됩니다.

단, 피벗에 따라 수행시간에 차이가 생길 수 있으니 그건 고려하면서..

간단히 말하면 퀵 정렬은 이 피벗을 기준으로 작은 것은 왼쪽으로, 큰 것은 오른쪽으로 몰아 넣는 방식입니다.

○ 과정

1. 분할 (divide)

- LT (피벗보다 작은 원소들)

- EQ (피벗과 같은 원소들)

- GT (피벗보다 큰 원소들)

2. 재귀 (recur)

: LT, GT 를 재귀하면서 정렬

3. 통치 (conquer)

: LT, EQ, GT를 합칩니다.

○ 수도코드입니다.

Alg quickSort(L)

	if(L.size() > 1)
		k <-- a position L
		(LT, EQ, GT) <-- partition(L, k)
		quickSort(LT)
		quickSort(GT)
		L <-- merge(LT, EQ, GT)
	return

○ 성능

최악의 성능을 생각하면, 하나 바꾸고 재귀하고, 하나 바꾸고 재귀하고... n^2이 될것이다.

하지만 이럴 확률은 매우 드물고 평균적으로는 O(n log n)의 성능의 속도를 갖는다.

--> "최선실행시간"

O(n log n)이 나오는 이유 : 합병 정렬과 같이 과정을 나열한다고 생각하면 높이 n log n이 된다.