퀵정렬(Quick Sort)

퀵정렬(Quick Sort)

퀵정렬은 분할정복 알고리즘으로, 병합정렬과 달리 비균등하게 분할하고 병합해 나갑니다.

과정

1. 리스트안에 하나의 원소을 고른다. 이때 이 원소를 pivot 이라고 한다.
2. pivot을 기준으로 피봇보다 작은건 왼쪽으로, 큰건 오른쪽으로 옮겨진다.
3. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하기 위해 분할된 리스트들에 대해 1, 2번과정을 반복한다.
4. 더이상 분할이 불가능할때까지 반복한다

예시로 알아보는 퀵정렬

1. 처음 pivot = 3으로 설정한뒤 3을 기준으로 왼쪽과 오른쪽을 정렬한다.
2. pivot을 기준으로 두개의 리스트로 나눠진 부분에서 각각 1과 6을 pivot으로 정한뒤 왼쪽과 오른쪽으로 정렬한다.
3. 이런 과정을 더이상 분할이 불가능할때까지 반복한다

퀵정렬 코드

def quick_sort(arr, left, right):
    if left < right:
        pivot = hoare_partition(arr, left, right)
        quick_sort(arr, left, pivot - 1)
        quick_sort(arr, pivot + 1, right)
    return arr

# 피봇찾기
def hoare_partition(arr, left, right):
    L = left  # 부분리스트의 가장 앞
    R = right  # 부분리스트의 가장 뒤
    pivot = arr[left]  # 처음 피봇은 가장 앞에있는값으로 시작
    while L <= R:
        while arr[L] <= pivot:
            L += 1
        while arr[R] > pivot:
            R -= 1
        if L < R:
            arr[L], arr[R] = arr[R], arr[L]
    arr[left], arr[R] = arr[R], arr[left]
    return R

arr = [3,2,4,6,9,1,8,7,5]
quick_sort(arr,0,len(arr)-1)

퀵정렬의 특징

장점

• 퀵정렬은 말그대로 굉장히 빠른 정렬알고리즘이다 평균적으로 O(n log n)의 시간복잡도를 가진다

단점

• 최악의 경우에는 O(n^2)의 시간복잡도를 보일수도 있다.