Quick Sort
[출처 : 위키피디아]
- 분할정복(divide and Conquer) 방법을 통해 리스트를 정렬한다.
- 리스트 가운데서 하나의 원소를 고른다 이 원소를 pivot이라 한다.
- 분할(divide) : 피벗 앞엔 피벗보다 작은 값이, 뒤엔 큰 값이 오도록 피벗을 기준으로 리스트를 둘로 나눈다.
- 분할된 두개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복한다.
복잡도 -
최악의 경우 :
최선의 경우 :
구현 -
결과 -
반응형