정렬(Sorting) - 퀵 정렬 (Quick Sort)

pivot, i, j를 이용하여

i는 왼쪽에서 오른쪽으로 이동하며 pivot보다 큰 값을 찾고

j는 오른쪽에서 왼쪽으로 이동하며 pivot보다 작은 값을 찾은 후

a[i] a[j]를 swap

i를 기준으로 분할 (Partition) 후 단계 반복

 

평균 수행시간 최소

순환호출 사용

[1]	[2]	[3]	[4]	[5]	[6]	[7]	[8]	[9]	[10]	left	right
(26	5	37	1	61	11	59	15	48	19)	1	10
↑ pivot		↑ i							↑ j
		19							37
				↑ i			↑ j
				15			61
pivot					i	j
(11	5	19	1	15)	26	(59	61	48	37)
(11	5	19	1	15)						1	5
(1	5)	11	(19	15)
1	5									1	2
			15	19						4	5
						(59	61	48	37)	7	10
						(48	37)	59	(61)
						37	48			7	8
									61	10	10
1	5	11	15	19	26	37	48	59	61	결과

 

 

분석

최악 : 리스트가 이미 정렬된 경우 → O($n^2$)

최선 : 리스트가 항상 반으로 나누어 질 때 → O(n log n)

          T(n) ≤ cn + 2T(n/2)     (어떤 상수 c에 대해)

                ≤ cn + 2(cn/2 + 2T(n/4))

                ≤ 2cn + 4T(n/4)

                ...

                ≤ cn log n + nT(1) = O(n log n)

평균 : O(n log n)

 

 

개선

pivot 선택시 중간값 규칙 적용

 

dyeoma.tistory.com/41

퀵 정렬 (Quick Sort)