퀵정렬 구현

면접 등에서 가장 많이 출제되는 퀵정렬을 직접 구현해봐야겠다고 생각했다.

가장 빠르다고 알려진 퀵정렬
시간 복잡도는 다른 분할정복 정렬과 다르지 않은데
메모리 locality 때문에 비교적 더 빠른 시간내에 정렬이 가능하다.

하지만 pivot을 지정하는데, 데이터의 상태와 pivot의 선택에 따라 시간복잡도가 달라진다.

때문에 O(nlogn) 에서 O(n^2) 까지도 시간복잡도가 올라갈 수 있다.

구현 논리는 pivot을 지정해주고, 그 pivot 을 기준으로 pivot보다 작은 값을 왼쪽으로 몰아놓고, 오른쪽으로 pivot보다 큰 값을 모아준다.

왼쪽으로 몰린 리스트에서 다시 pivot을 지정하고, 위의 과정을 반복한다.

def partition(quick_list, start, end):
    # 피벗 기준으로 더 작은 값들을 왼쪽으로 보내고,
    # 큰 값은 오른쪽으로
    pivot = quick_list[start]
    left= start + 1
    right = end

    done = False

    while not done:
        while left <= right and quick_list[left] <= pivot:
            left += 1

        while left <= right and quick_list[right] > pivot:
            right -= 1

        if left > right:
            done= True
        else:
            quick_list[left], quick_list[right] = quick_list[right], quick_list[left]
        # left 와 right에서 한칸씩 안 쪽으로 온다.
        #  quick_list[left] 값이 pivot 보다 작으면 그대로 두고 left 포인터만 이동한다. 크다면 left 값 고정 해 두고
        # right 값을 마찬가지로 옮겨준다. right에서 pivot 보다 작은 값을 찾았다면 그 값과 left 값을 바꾸어준다.
    quick_list[start], quick_list[right] = quick_list[right], quick_list[start]
    // 마지막에 pivot 값과 right 마지막
    return right

def quick(list1, start, end):
        if  start < end:
            pivot = partition(list1, start, end)
            quick(list1, start, pivot - 1) // 왼쪽 리스트
            quick(list1, pivot + 1, end)
        return list1

def solution():
    seq= [3,4,5,2,41,56,56,4576]
    return quick(seq, 0, len(seq)-1)

print(solution())

위 처럼 파이썬으로 구현할 수 있다.