퀵 정렬(Quick sort)

퀵 정렬이란?

분할 정복 알고리즘의 하나, 평균적으로 매우 빠른 수행속도를 자랑하는 정렬방법

알고리즘 개념요약

• 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속함
• 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 자랑하는 정렬 방법

1. 리스트 안에있는 한 요소를 선택. 이렇게 고른 원소를 피벗이라 한다.
2. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 오른쪽으로 옮겨진다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬
   • 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복
4. 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복
   • 리스트 크기가 0이나 1이 될 때까지 반복

특징

• 장점
  • 속도가 빠르다.
  • 추가 메모리 공간을 필요로 하지 않는다.
• 단점
  • 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

시간복잡도

• O(nlog2n)