Quick Sort - 퀵정렬

by Yaboong on February 18, 2018

개요

• Quick sort 파티셔닝 설명 및 구현 예제
• 코드 보기

Quick Sort

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

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

Partition 과정

비교

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

삽입정렬 합병정렬 퀵정렬 비교

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

구현 - Java

github 에서 보기

참고한 자료

• Princeton Algorithms Course 7 1 Quicksort 19 33