알고리즘 - 퀵 정렬(Quick Sort)

단순 비교를 이용한 정렬을 수행.

 

분할 정복 알고리즘의 일종으로 엄청 빠름.

이후 나올 합병정렬(Merge Sort)와는 다르게 '비균등'하게 분할한다.

 

1. 기준점,피벗(Pivot)을 고른다.

2. 피벗을 기준으로 작은건 왼쪽, 큰건 오른쪽으로 전부 옮긴다.

3. 피벗을 제외하고 분할된 왼쪽 리스트, 오른쪽 리스트에 대해 각각 1~2를 반복.

4. 리스트가 더 안쪼개질때까지 반복(리스트 크기가 0이나 1이 될 때)

5. 끝내면 완성!

 

기본 연산.

분할 : 피벗을 기준으로 입력 배열(리스트)를 2개로 나눔.

정복 : 분할된 배열을 정렬. 배열이 크면 순환호출을 이용해 다시 분할.

결합 : 정렬이 끝난 부분 배열을 하나의 배열로 합친다.

 

 

장점 : 속도가 빠름. 정렬 알고리즘 중 최고속.  추가 메모리 공간이 필요 없다. 

 

단점 : 정렬되어있는 리스트에 대해서는 오히려 수행이 더 걸림.