[Algorithm] Quick Sort(퀵 정렬)

mingreen·2021년 6월 3일
0

Algorithm

목록 보기
4/4

Quick Sort

퀵 정렬은 divide-and-conquer 방법을 사용한 정렬로, 현재 배열에서 기준 값을 정하고 그 값 보다 작은 배열/큰 배열로 분리하면서 진행한다.

구현 방법

0번 인덱스의 원소를 pivot으로 설정하고, pivot 값보다 작거나 같은 값을 앞으로 큰 값을 뒤로 옮긴 후 분할한다. 한 cycle이 돌고나면 pivot이 되는 값은 최종적으로 위치가 결정되는 방법이다.

구현(Python)-1

pivot 보다 작은 값/큰 값에 해당하는 리스트를 각각 만들어서 구현.
pivot이 생길 때마다 리스트가 생성되어서 메모리 낭비가 발생한다.
따라서, 구현-2의 in-place 방법으로도 구현해보았다.

import time

def quicksort(test):
    if len(test) == 1: return test
    pivot_idx = len(test)//2
    pivot = test[pivot_idx]
    pivot_min = []
    pivot_max = []
    for i in test[0:pivot_idx]+test[pivot_idx+1:]:
        if i >= pivot : pivot_max.append(i)
        elif i < pivot : pivot_min.append(i)

    return quicksort(pivot_min) + [pivot] + quicksort(pivot_max)


if __name__ == '__main__':
    start = time.time()  # 시작 시간 저장
    test = [4,6,2,8,9,7,1]
    print(quicksort(test))
    print("time1 :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

결과 - 1

[1, 2, 4, 6, 7, 8, 9]
time1 : 3.1948089599609375e-05

구현(Python)-2

import time

def quicksort(test, start, end):
    if start >= end: return
    pivot = test[start]
    left = start + 1
    right = end

    while left <= right:
        while test[left] <= pivot:
            left += 1
        while test[right] > pivot:
            right -= 1
        if left <= right:
            test[left],test[right] = test[right], test[left]
        else: break

    test[right], test[start] = test[start],test[right]
    quicksort(test, start, right-1)
    quicksort(test, right+1, end)


if __name__ == '__main__':
    start = time.time()  # 시작 시간 저장
    test = [4,6,4,2,8,9,7,1]
    quicksort(test, 0, len(test)-1)
    print(test)
    print("time1 :", time.time() - start)  # 현재시각 - 시작시간 = 실행 시간

결과 - 2

[1, 2, 4, 4, 6, 7, 8, 9]
time1 : 3.5762786865234375e-05

시간복잡도

불균형하게 분할되기 때문에 최악의 경우 1, n-1로 계속해서 분할하면 O(n^2)의 시간복잡도가 나온다.
하지만, 균형에 가깝게 분할되면 O(nlogn)의 시간복잡도를 가진다.

공간복잡도

구현 - 2를 기준으로 in-place sorting 이 발생하였기 때문에 O(n)이다.

profile
주니어 백엔드 개발자의 기록하는 습관 만들기🧑‍💻

0개의 댓글