퀵 정렬은 다른 정렬 알고리즘에 비해 아주 준수한 수행 시간을 보이기 때문에 가장 많이 사용하는 정렬 알고리즘 중 하나이다. 병합 정렬과 마찬가지로 분할 정복과 재귀 알고리즘을 이용한다.
unstable 하며 알고리즘이 호출될 때마다 새로운 리스트를 생성하며 리턴하기 때문에 기본적으로는 not-in-place 정렬이기도 하다. 다만, 배열의 인덱스를 활용하여 주어진 배열 내에서만 원소를 이동시킨다면 효율적인 메모리 활용이 가능하기 때문에 in-place 정렬이라고 할 수 있다.
1. 배열 내 원소 중 하나를 pivot(축)으로 설정한다.
2. 나머지 원소를 pivot과 비교하며 pivot보다 작은 경우에는 pivot의 앞쪽에, 큰 경우에는 뒤쪽에 위치시킨다.
3. pivot을 기준으로 양쪽에 위치한 각각의 리스트 내에서 위의 과정을 반복한다.
O(N)
의 공간 복잡도를 갖는다. 하지만, 주어진 배열 내에서 원소가 이동하는 in-place sorting 방식으로 구현할 경우, O(1)
의 공간 복잡도를 가진 코드 구현이 가능하다.O(NlogN)
의 시간 복잡도를 갖는다. 하지만, 분할된 값들이 한 쪽으로 치우치게 된다면 결국 모든 값에 대하여 비교가 필요하므로 O(N^2)
만큼의 시간이 소모된다.O(NlogN)
의 시간 복잡도를 보인다.def quick_sort(arr, first, last):
if first >= last:
return
mid = partition(arr, first, last)
quick_sort(arr, first, mid-1)
quick_sort(arr, mid, last)
return arr
def partition(arr, first, last):
pivot = arr[(first + last) // 2]
while first <= last:
while arr[first] < pivot:
first += 1
while arr[last] > pivot:
last -= 1
if first <= last:
arr[first], arr[last] = arr[last], arr[first]
first, last = first + 1, last - 1
return first
--