퀵정렬 알고리즘(Quick Sort)
- 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 알고리즘 이다.
- 분할 정복
- 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략
- 대개 순환 호출을 이용하여 구현된다.
과정
[ 5, 1, 2, 8, 7, 3, 9, 6, 10, 4 ]
위와 같은 배열이 존재 할때,
- 리스트 안에 있는 한 요소를 선택한다. 일반적으로 가장 첫번째 요소를 선택한다.
- 피벗을 제외하고 오른쪽으로 요소를 이동하면서, 피벗보다 큰 수를 만나면, 해당요소 선택
- 리스트의 끝에서부터 왼쪽으로 이동하면서, 피벗보다 작은 수를 만나면, 해당 요소를 선택
- 2번, 3번의 선택된 요소의 index가 2번 <= 3번 (엇갈리는 경우) 피벗과 3번 선택된 요소와 Swap한다.
- 2번, 3번의 선택된 요소의 index가 2번 > 3번 2번 3번에서 선택된 요소를 Swap한다.
- 피벗을 기준으로 왼쪽과 오른쪽에 놓여진 리스트들을 다시 퀵정렬을 호출한다.
예제
빨강(피벗)
초록(왼쪽 선택요소)
보라(오른쪽 선택요소)
[ 5 , 1 , 2 , 8 , 7 , 3 , 9 , 6 , 10 , 4 ]
[ 5 , 1 , 2 , 4 , 7 , 3 , 9 , 6 , 10 , 8 ]
[ 5 , 1 , 2 , 4 , 7 , 3 , 9 , 6 , 10 , 8 ]
[ 5 , 1 , 2 , 4 , 3 , 7 , 9 , 6 , 10 , 8 ]
[ 5 , 1 , 2 , 4 , 3 , 7 , 9 , 6 , 10 , 8 ]
[ 3 , 1 , 2 , 4 , 5 , 7 , 9 , 6 , 10 , 8 ]
[ 3 , 1 , 2 , 4 ][ 5 ] [ 7 , 9 , 6 , 10 , 8 ]
[ 3 , 1 , 2 , 4 ][ 5 ] [ 7 , 9 , 6 , 10 , 8 ]
[ 2 , 1 , 3 , 4 ][ 5 ] [ 7 , 6 , 9 , 10 , 8 ]
[ 2 , 1 ][ 3 ] [ 4 ][ 5 ] [ 7 , 6 , 9 , 10 , 8 ]
[ 2 , 1 ][ 3 ] [ 4 ][ 5 ] [ 6 , 7 , 9 , 10 , 8 ]
[ 2 ][ 1 ] [ 3 ][ 4 ] [ 5 ][ 6 ] [ 7 ][ 9 , 10 , 8 ]
....
[ 2 ][ 1 ] [ 3 ][ 4 ] [ 5 ][ 6 ] [ 7 ][ 8 ] [ 9 ][ 10 ]
알고리즘 구현
def solution(array):
answer = []
print(array)
quicksort(array,0, len(array)-1)
answer = array
return answer
def quicksort(array,start,end):
if start>= end:
return
pivot = start
left = start + 1
right = end
while left <= right:
while left<=end and array[left]<array[pivot]:
left += 1
while right>start and array[right] > array[pivot]:
right -= 1
if left >= right:
array[right], array[pivot] = array[pivot], array[right]
else:
array[left], array[right] = array[right], array[left]
quicksort(array,start,right-1)
quicksort(array,right+1,end)시간 복잡도 O(N LogN)
요소의 개수 N이 2의 거듭제곱이라고 가정할때(N = 2^K), 순환 호출 깊이는 (K = logN) 이고, 각 순환 호출에서는 대부분의 레코드를 비교해야하므로 평균 N번의 비교가 이루어진다.
따라서, 평균적으로 N logN의 시간 복잡도를 같는다
