Quick Sort(퀵소트)

실제 가장 빠른 정렬 알고리즘

전형적인 divide-and-conquer 알고리즘 중 하나 

pivot보다 작은 값들을 리스트의 왼쪽으로, 큰 값들은 리스트의 오른쪽으로 재배열 한 후, 양 쪽을 재귀적으로 다시 정렬

 

퀵 정렬 코드(python)

Pyyhon으로 작성한 퀵소트

 

---

 퀵 정렬 구현 방법

 

 

초기상태

• 입력이 주어진 정렬해야 할 배열이다.
• 피벗은 arr[0], left와 right도 정의되어 있다.

1.

• left: 피벗 보다 큰 값이 나올 때까지 left++한다. 5>4이기 때문에 left는 더 이상 이동하지 않는다.
• right: 피벗보다 작은 값이 나올 떄까지 right --한다. 7>4이기 때문에 right--한다.

2.

• left: 이동이 없었다.
• right: 피벗보다 작은 3이 나오니 드디어 멈췄다.

3. left<=right이기 떄문에 arr[left]와 arr[right]를 swap한다.

4&5. left와 right가 조건에 맞게 이동을 하다가 멈추면 자리 swap 

 

7.

• left와 right가 더 이상 이동할 수 없는 상황
• 노란부분: 피벗보다 모두 작은 부분
• 파란부분: 피벗보다 모두 큰 부분

8.

• 피벗의 위치와 left의 위치를 swap한다.
• 피벗보다 작은 부분(노란 부분) - 피벗 - 피벗보다 큰 부분(파란 부분) 순으로 정렬되는 모습을 볼 수 있다. 

 

9. 이제 각 노란 부분, 파란 부분 각각 또 quick sort를 진행한다.

 

---

시간 복잡도

 

S

P

L

p(pivot)을 기준으로 S는 P보다 작은 부분, L은 P보다 큰 부분

 

T(n) = T(|S|) + T(|L|) + c*n

#c*n번 비교를 통해 S P L을 분류 

 

Worst Case - S 또는 L이 0인 경우. 이미 정렬된 것이 들어옴

T(n) = T(n-1) + c*n  

=O(n^2)

 

Best Case - Average Case

T(n) = T(n/2) + T(n/2) + c*n = 2T(n/2) + c*n

=O(nlogn)

---

특징

장점

• 속도가 빠르다.
• 시간 복잡도가 O(nlog₂n)를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.
• in-place로, 추가 메모리 공간을 필요로 하지 않는다. 
• 퀵 정렬은 O(log n)만큼의 메모리를 필요로 한다.

단점

• 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
• 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
  EX) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택한다.

 

---

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

https://www.youtube.com/channel/UCJ4SXKMLQucqaxt4A6PonwQhttps://www.youtube.com/channel/UCJ4SXKMLQucqaxt4A6PonwQ