[Sort] Quick Sort (퀵 정렬)

분할정복 알고리즘을 이용하여, 기준점(피봇)을 잡고 왼쪽, 오른쪽을 나누어 각각 정렬한다.

 

정의

• 리스트에서 기준점을 설정한다. 리스트를 순회하며 기준점보다 작은 원소는 왼쪽에, 큰것을 오른쪽에 둔다.

 

설명

• 퀵정렬은 리스트가 고정 크기인 경우(대부분의 프로그래밍 언어)와 가변 리스트인 경우(파이썬)으로 나눌 수 있다.
• 파이썬 같은 경우 분할정복 아이디어로 피봇 보다 작은 원소, 피봇보다 큰 원소를 각각 새로운 리스트로 만들어서 합치는 방법으로 한다.
• 이외의 경우, 투포인터를 이용하여 좌, 우에서 피벗쪽으로 탐색을 진행하고 L, R이 교차될 때까지 탐색하며 자리를 교환한다.
• 피봇은 0번 인덱스, 중간 인덱스, 마지막 인덱스 무엇으로 잡아도 상관 없으나 파이썬 알고리즘에는 0번 인덱스로 잡는 것이 가장 편하다.
• 퀵 정렬을 처음 배운다면 파이썬 버전으로 보는 것을 추천한다. 이해하기가 가장 쉽다!

 

시간복잡도

• 평균 : O($logn$)
• 최악 : O($n^2$)

 

구현

✅ only 파이썬 (가변 리스트)

def QuickSort(numbers):
    # 길이가 0,1 이면 정렬 필요 없이 그대로 리턴(베이스 케이스)
    if len(numbers) < 2:
        return numbers

    # 길이가 2 이상이라면 아래 과정을 수행
    # 왼, 오, 피벗 지정
    left = []
    right = []
    pivot = numbers[0]

    # numbers의 길이만큼 순회, 0은 위에서 피벗으로 고정했으니까 1부터 순회
    for i in range(1, len(numbers)):
        # 피벗보다 크거나 같으면 오른쪽
        if numbers[i] >= pivot:
            right.append(numbers[i])
        # 피벗보다 작으면 왼쪽
        else:
            left.append(numbers[i])

    # 나누어진 왼쪽, 오른쪽에 대해서 퀵정렬을 다시 수행한다.
    # 왼, 오가 각각 자신의 피벗,왼,오를 지정하고 위 과정을 반복하여 최종 결과물을 return 한다.
    return [*QuickSort(left)] + [pivot] + [*QuickSort(right)]

 

 

✅ 범용 (고정 리스트)

def GeneralQuickSort(numbers, start, end):
    if start < end:
        p = Partition(numbers, start, end)
        GeneralQuickSort(numbers, start, p-1)
        GeneralQuickSort(numbers, p+1, end)
    return numbers

def Partition(numbers, start, end):
    # 왼,오,피봇은 numbers의 인덱스
    pivot = start
    L = start + 1
    R = end
    done = False # 분할 완료 플래그

    while not done:
        # 피봇을 기준으로 작은건 왼쪽 큰건 오른쪽에 모이도록 교환한다.
        while L <= R and numbers[L] <= numbers[pivot]: L += 1
        while L <= R and numbers[R] >= numbers[pivot]: R -= 1

        if L < R:
            numbers[L], numbers[R] = numbers[R], numbers[L]
        # 모든 교환이 일어나서 L과 R이 교차되면 교환을 종료한다.
        else:
            done = True

    # 교환이 종료된 경우 작은게 모여있는 왼쪽, 큰게 모여있는 오른쪽 중간에 피벗을 위치시켜야 한다.
	# 위에서 종료된 경우, 0~R까지는 은 피벗보다 작은 값들이 있고
	# R+1부터 끝까지는 피벗보다 큰 수가 위치한다.
	# 즉 R과 피벗을 교환하여 피벗의 위치를 고정 시키고 피벗 좌우로 작은값/큰값이 분할 완료한다.
    numbers[pivot], numbers[R] = numbers[R], numbers[pivot]
    return R