퀵 정렬 (Quick Sort) 란?

퀵 정렬이란?

하나의 배열을 피벗(pivot) 을 기준으로 두 개의 비균등한 배열로 분할하고

분할된 부분 배열을 정렬한 다음

두 개의 정렬된 배열을 합하여 전체 정렬된 배열이 되게하는 방법이다.

 

퀵 정렬은 3단계로 이루어졌다. 

 

• 분할 단계 : 입력 배열을 피벗을 기준으로 비균등하게 2개의 부분 배열로 분할한다.
  1. 피벗을 중심으로 왼쪽 : 피벗보다 작은 요소들
  2. 피벗을 중심으로 오른쪽 : 피벗보다 큰 요소들
• 정복 단계 : 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 '순환 호출' 을 이용하여 다시 분할 정복 방법을 적용한다.
• 결합 단계 : 정렬된 부분 배열들을 하나의 배열로 합병한다.

 

퀵 정렬 장단점은 ?

속도가 빠르다는 장점을 갖고 있다. 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.

또한 추가 메모리 공간을 필요로 하지 않는다. 메모리공간 복잡도는 O(logN) 이다.

 

하지만, 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

 

따라서, 불균형 분할을 어느정도 방지하기 위하여 피벗을 선택할 때 균등하게 분할할 수 있는 데이터(중간 값)를 선택해야한다.

 

 

시간 복잡도는 ?

평균적으로 O(nlogN)의 복잡도를 갖는다. 또한 O(nlogN)을 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.

왜냐하면 불필요한 데이터의 이동을 중리고 먼 거리의 데이터를 교환할 뿐만 아니라,

한 번 결정된 피벗들이 추후 연산에서 제외되는 특성 때문이다.

 

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