퀵 정렬(Quick sort)

퀵정렬

시간복잡도	공간복잡도
모든 값을 비교해야하므로 N 반복을 거듭할 때마다 반씩 줄어듦으로 log N O(N log N)	배열을 병합할 때 병합 결과를 담아놓을 배열이 필요함 O(N)

 

일반적으로 pivot이라고 부르는 임의의 기준값을 정하고 pivot보다 큰 값, 작은 값을 정렬하는 알고리즘. 분할 정복과 재귀용법을 사용.

 

[6, 3, 1, 4, 5,  2, 7]

 

예를 들어 이렇게 주어진 배열을 정렬한다고 해보자.

 

먼저 기준이 될 pivot을 결정한다. 간단하게 첫번째 요소를 pivot으로 결정해보자.

  ☝퀵정렬은 어떤 값이 pivot으로 설정되냐에 따라 성능이 큰 영향을 받는다. 최악의 경우 시간 복잡도가 O(N²)이 될 수도 있다. 그래서 보통 pivot 값은 배열의 첫 값, 중간 값, 마지막 값 중에 크기가 중간인 값을 사용한다.

[6, 3, 1, 4, 5,  2, 7]
 ^

 

이제 pivot을 기준으로 작은 값과 큰 값, 같은 값을 비교하여, 배열을 분할한다.

[6, 3, 1, 4, 5,  2, 7]
 ^
 
 less = [3, 1, 4, 5, 2]
 equal = [6]
 great = [7]

 

그리고 분할된 각 배열 안에서 다시 pivot을 결정하여 값을 비교하고 배열을 분해한다.

[3, 1, 4, 5, 2]
 ^
 
 less = [1, 2]
 equal = [3]
 great = [4, 5]

 

이런 방식으로 재귀호출한다. 주어진 배열의 길이가 2보다 작다면 정렬할 필요가 없으므로 재귀호출의 탈출조건으로 사용한다. 모든 요소를 정렬한후 다시 합친다

[3, 1, 4, 5, 2]
 ^
 
 less = quick_sort([1, 2])
 equal = quick_sort([3])
 great = quick_sort([4, 5])
 
return less + equals + greater

 

 

 

구현

def quick_sort(input_array):
    if len(input_array) < 2:
        return input_array

    less_array = []
    equals_array = []
    greater_array = []

    pivot = input_array[0]

    for num in input_array:
        if pivot > num:
            less_array.append(num)
        elif pivot < num:
            greater_array.append(num)
        else:
            equals_array.append(num)

    less_array = quick_sort(less_array)
    greater_array = quick_sort(greater_array)

    return less_array + equals_array + greater_array


if __name__ == '__main__':
    print(quick_sort([6, 3, 1, 4, 5,  2, 7]))

두 배열을 비교하는 while문에서는 배열 안의 값을 빼고 넣는 것보다 l, h의 임시 인덱스를 사용하여 효율적으로 비교한다.

 

다만 파이썬의 split은 매번 배열을 복사하여 반환하므로 메모리 사용효율이 떨어진다.

 

최적화

  위의 구현은 내부적으로 less, greater, equals 세 개의 배열을 사용하는데, 주어진 배열 내부에서 정렬하게 되면 추가 배열 사용 없이 공간복잡도를 O(1)로 만들 수 있다.

def quick_sort(input_array):
    def sort(low, high):
        if high <= low:
            return
        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        pivot = input_array[(low + high) // 2]
        while low <= high:
            while input_array[low] < pivot:
                low += 1
            while input_array[high] > pivot:
                high -= 1
            if low <= high:
                input_array[low], input_array[high] = input_array[high], input_array[low]
                low, high = low + 1, high + 1
        return low
    return sort(0, len(input_array) - 1)

 

 

 

참고

https://www.dalecoding.com/algorithms/quick-sort

퀵 정렬 (Quick Sort) | 달레코딩