Quick Sort

주어진 배열을 한번 섞는다.
pivot (기준값) 을 하나 설정하고, pivot 의 왼쪽에는 pivot 보다 작은 값들이, 오른쪽에는 pivot 보다 큰 값들이 오도록 partition 한다.
왼쪽, 오른쪽으로 나뉜 배열에 대해 재귀적으로 반복한다.

평균적으로 O(nlogn), 최악의 경우(이미 정렬된 경우) O(n²). 최악의 경우를 피하기 위해 Shuffle 해주는 것.

삽입정렬, 합병정렬과의 비교

Good algorithms are better than supercomputers.
Good algorithms are better than good ones. – Robert Sedgewick 교수님 가라사대

Yaboong

오스카 쉰들러는 흔해빠진 기회주의자요 부패한 사업가였다. 그러나 거대한 악이 세상을 점령하는 것처럼 보일 때 그 악에 대항해서 사람의 생명을 구한 것은 귀족도 지식인도 종교인도 아닌 부패한 기회주의자 오스카 쉰들러였다.

Seoul, South Korea

YABOONG