[알고리즘] 퀵 정렬

퀵 정렬

정렬 알고리즘 중에서 가장 많이 사용되는 알고리즘이며 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 되는 알고리즘이다.

퀵 정렬은 '피벗'이라는 기준을 가지고 피벗보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법을 사용한다. 동작 방법은 아래와 같다.

 

1. 리스트에서 첫 번째 데이터를 피벗으로 설정한다.

2. 리스트의 왼쪽에서부터 피벗보다 큰 데이터를 찾는다.

3. 리스트의 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.

4. 작은 데이터와 큰 데이터가 서로 엇갈린 위치에서 발견되었다면 작은 데이터와 피벗의 위치를 바꾼다.

5. 엇갈리지 않았다면 작은 데이터와 큰 데이터의 위치를 바꾼다.

예시

숫자 10, 20, 6, 39, 40, 1, 16, 9가 순서대로 저장되어 있다.

준비된 데이터

리스트의 첫 번째 데이터는 숫자 10이다. 10을 피벗으로 설정하고 왼쪽에서부터 10보다 큰 데이터와 오른쪽에서부터 10보다 작은 수를 찾자.

첫 번째 교환

왼쪽에서부터 피벗인 10보다 큰 데이터를 찾으면 20이고 오른쪽에서부터 피벗인 10보다 작은 데이터를 찾으면 9이다.

두 데이터는 서로 엇갈리지 않았기 때문에 작은 데이터와 큰 데이터의 위치를 바꿔준다.

두 번째 교환

왼쪽에서부터 피벗인 10보다 큰 데이터는 39이고, 오른쪽에서부터 피벗인 10보다 작은 데이터는 1이다. 

두 데이터는 서로 엇갈리지 않았기 때문에 작은 데이터와 큰 데이터의 위치를 바꿔준다.

세 번째 교환

왼쪽에서부터 피벗인 10보다 큰 데이터는 40이고, 오른쪽에서부터 피벗인 10보다 작은 데이터는 1이다.

두 데이터는 서로 엇갈린 위치에 존재하기 때문에 작은 데이터인 1과 피벗인 10의 위치를 바꿔준다.

엇갈린 위치 교환 후 데이터

위의 과정을 반복하면 정렬된 데이터를 얻을 수 있다.

정렬 완료된 데이터

코드

1. 퀵 정렬 코드

def quick_sort(start, end, array):
    ##  원소가 1개인 경우 종료
    if start >= end:
        return
    
    pivot = start   ## 피벗은 첫 번째 원소부터 시작
    left = start + 1
    right = end

    while left <= right:
        # 왼쪽부터 피벗보다 큰 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 오른쪽부터 피벗보다 작은 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        # 작은 데이터와 큰 데이터가 서로 엇갈렸을 때
        if left > right:
            # 작은 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
        # 엇갈리지 않았을 때
        else:
            # 작은 데이터와 큰 데이터를 교체
            array[left], array[right] = array[right], array[left]
    
    quick_sort(start, right-1, array)
    quick_sort(right + 1, end, array)

2. 파이썬의 장점을 살린 코드

def quick_sort(array):
    # 리스트에 1개의 데이터만 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0]    # 피벗은 첫 번째 데이터
    tail = array[1:]    # 피벗을 제외한 리스트

    # 분할된 왼쪽 데이터
    lef_side = [x for x in tail if x <= pivot]  
    # 분할된 오른쪽 데이터
    right_side = [x for x in tail if x > pivot]

    return quick_sort(lef_side) + [pivot] + quick_sort(right_side)

시간 복잡도

퀵 정렬의 평균 시간 복잡도는 $O(NlogN)$이다. 하지만 최악의 경우 $O(N^2)$의 시간 복잡도를 갖는다.

정리

1. 퀵 정렬은 정렬 라이브러리의 근간이 되는 알고리즘이다.

2. '피벗'을 기준으로 작은 데이터와 큰 데이터를 찾아 위치를 바꾼다.

3. 퀵 정렬은 평균적으로 $O(NlogN)$의 시간 복잡도를 갖는다.

4. 최악의 경우 $O(N^2)$의 시간 복잡도를 갖는다.