분할 정복 알고리즘 중 하나, 평균적으로 매우 빠른 수행 속도를 자랑한다
분할 정복 알고리즘
문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
•
시간 복잡도 : Average O(nlogn) / Worst O(n^2) - 이미 정렬된 배열을 정렬할 경우
•
공간 복잡도
Process
1.
리스트 내 한 요소를 피벗으로 지정한다.
2.
피벗을 기준으로 피벗보다 작은 요소들은 피벗의 왼쪽으로, 큰 요소들은 피벗의 오른쪽으로 이동시킨다.
3.
피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 나눈다.
4.
각 리스트를 1 - 3 과정을 반복한다.
Quick Sort는 두 가지 방법이 있다.
Not In Place
1.
기준 피벗을 하나 고른다.
2.
배열을 돌면서 피벗보다 작은 요소의 배열, 피벗보다 큰 요소의 배열 두 가지로 분할한다.
3.
하위 배열에 대해 재귀적으로 quick 정렬을 호출한다.
특징 : 별도의 메모리 공간이 필요하므로 데이터의 양이 많으면 공간적인 낭비가 심함, 안정 정렬
In Place
1.
가운데 요소를 피벗으로 정한다.
2.
인덱스를 앞과 뒤, 두 개를 사용하여 배열의 처음과 끝을 비교해나간다.
3.
앞의 인덱스가 피벗보다 큰 수를 가리키고, 뒤의 인덱스가 피벗보다 작은 수를 가리키면 두 요소를 스왑한다.
4.
두 인덱스가 만날 때까지 진행
5.
피벗의 앞과 뒤 두 배열로 나눠 앞의 과정을 재귀적으로 반복한다.
특징: 스왑으로 인핸 불안정 정렬, 추가적인 공간이 필요하지 않아 공간 절약 가능