[정렬] 퀵 소트

퀵소트란?

분할 정복 방법을 통해 주어진 배열을 정렬한다.
불안정 정렬에 속하며 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. Merge Sort와 달리 Quick Sort는 배열을 비균등하게 분할한다.

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?
왼쪽에서 부터 피벗보다 큰 데이터를 찾고 오른쪽에서부터 피벗보다 작은 데이터를 찾고 그 둘을 교환하자

과정

1. 배열 가운데서 하나의 원소를 고른다. 이를 피벗이라 한다.

보통 리스트에서 첫 번째 데이터를 피벗으로 정한다. 👉 호어분할 방식

 

2. 피벗 앞에는 피벗보다 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눈다.

👉 배열을 둘로 나누는 것 분할(Divide), 파티션(Partition)이라고 한다. 분할을 마친 뒤 피벗은 위치가 바뀌지 않는다. 

 

3. 분할된 두 개의 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다.

 

📌 재귀 호출이 한번 진행될 때마다 최소한 하나의 원소는 최종적으로 위치가 정해지기때문에 이 알고리즘은 반드시 끝난다는 것을 보장할 수 있다. 퀵 정렬은 현재 리스트의 데이터 개수가 1인 경우에 끝난다.

시간복잡도

평균의 경우 : T(n) = O(nlogn)

최선의 경우 : T(n) = O(nlogn)

순환 호출의 횟수: logn

각 호출의 비교연산: n

순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = nlog₂n

최악의 경우 : T(n) = O(n^2)

정렬하고자 하는 배열이 오름차순 정렬, 내림차순인 경우

순환 호출의 횟수 :n

각 호출의 비교연산: n

순환 호출의 깊이 * 각 순환 호출 단계의 비교 연산 = n^2

최악의 시간복잡도일 경우 개선시킬 방법

피벗 값이 최소나 최대값으로 지정되어 파티션이 나누어지지 않았을 때, O(n^2)에 대한 시간복잡도를 가진다.

배열에서 가장 앞에 있는 값과 중간값을 교환해준다면 확률적으로나마 시간복잡도 O(nlog₂n)으로 개선할 수 있다. 하지만, 이 방법으로 개선한다해도 Quick Sort의 최악의 시간복잡도가 O(nlog₂n)가 되는 것은 아니다.

 

공간복잡도

배열 안에서 교환을 통해 정렬이 수행되므로 O(n)

 

장점

불필요한 데이터의 이동을 줄이고 먼 거리의 데이터를 교환, 시간 복잡도가 nlogn으로 다른 정렬 알고리즘에 비교해 빠르다.

단점

불안정 정렬이다. 정렬된 배열에 대해서는 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.

직관적이고 많이 쓰는 퀵소트 코드

#가장 직관적인 형태의 퀵소트
array= [ 5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick(array,start,end):
    #재귀함수니까 종료조건 먼저 써준다
    if start >= end:
        return
    pivot = start
    left = start + 1
    right = end

    while left <= right:
        #피벗보다 큰 수를 찾을때까지(작거나 같을 때만 while문)
        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[right],array[left] = array[left],array[right]
        
        quick(array,start,right-1)
        quick(array,right+1,end)
    print(array)

quick(array,0,len(array)-1)

단계별 결과

[0, 1, 2, 4, 3, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 9, 7, 8]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

파이썬의 장점을 살린 퀵소트 코드

#파이썬의 장점을 살린 퀵소트
array= [ 5, 7, 9, 0, 3, 1, 6, 2, 4, 8]
def quicksort(array):
    #리스트가 하나의 데이터만 가지고 있으면 종료
    if len(array) <= 1:
        return array
    pivot = array[0]
    #피벗을 제외한 리스트
    tail = array[1:]

    #분할된 왼쪽 부분
    #피벗과 같거나 작은 수 모두 왼쪽에 
    left_side = [x for x in tail if x <= pivot]
    #피벗보다 큰 수는 모두 오른쪽에
    right_side = [x for x in tail if x > pivot]
    print(left_side,pivot,right_side)
    #분할 이후 왼쪽 오른쪽 각각 정렬 수행후 전체 리스트 반환
    return quicksort(left_side) + [pivot] + quicksort(right_side)


print(quicksort(array))

단계별 결과

[0, 3, 1, 2, 4] 5 [7, 9, 6, 8]
[] 0 [3, 1, 2, 4]
[1, 2] 3 [4]
[] 1 [2]
[6] 7 [9, 8]
[8] 9 []
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

단순하게 피벗보다 작은수는 모두 왼쪽에 피벗보다 큰수는 모두 오른쪽에

 

출처

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

퀵 정렬(Quick Sort) | 👨🏻‍💻 Tech Interview

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077 

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고