퀵 정렬(Quick Sort)

퀵 정렬

• 퀵 정렬은 불안정 정렬에 속한다.
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 자랑하는 정렬
• 분할 정복이란 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.
• 과정
  1. 리스트 안의 한 요소를 선택한다. 이를 피벗(pivot) 이라고 한다.
  2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 가고 피벗보다 큰 요소들은 모두 피봇기준 오른쪽으로 옮겨진다.
  3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
     • 분할된 부분 리스트에 대하여 재귀호출을 이용해 정렬을 반복
     • 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 좌, 우를 나눈다.
  4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복

 

 

퀵 정렬의 장점

• 속도가 빠르다 -  O(nlogn)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• 추가 메모리 공간을 필요로 하지 않는다.

 

퀵 정렬의 단점

• 정렬된 리스트에 대해서는 불균형 분할이 되기 때문에 오히려 수행시간이 더 많이 걸린다.

 

퀵 정렬의 최악을 면하기 위한 방법

1. 배열의 랜덤화

2. 랜덤 피벗 선택

3. 3개의 원소를 피벗 후보로 두고 그 중간 값을 선택

 

 

참고

gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

m.blog.naver.com/PostView.nhn?blogId=ljy9378&logNo=221508655059&proxyReferer=https:%2F%2Fwww.google.com%2F