[알고리즘][정렬] ③ 퀵 정렬 (Quick Sort) - Python

2021.07.10 - [알고리즘(Algorithm)] - [알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python

[알고리즘][정렬] ① 선택 정렬 (Selection Sort) - Python

2021.07.10 - [알고리즘(Algorithm)] - [알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python

[알고리즘][정렬] ② 삽입 정렬 (Insertion Sort) - Python

 

지난 글에서 살펴본 선택 정렬(Selection Sort)와 삽입 정렬(Insertion Sort)에 이어서 정렬 알고리즘 중 가장 많이 사용되는 퀵 정렬(Quick Sort)에 대해서 알아보겠습니다. 

 

1. 퀵 정렬(Quick Sort)이란?

- 퀵 정렬(Quick sort)는 영국의 컴퓨터 과학자  찰스 앤터니 리처드 호어가 1959년에 개발한 정렬 알고리즘으로, 피벗을 기준으로하여 좌우를 나누기 때문에 파티션 교환 정렬(Partition Exchange Sort)라고도 불립니다. 

- 피벗(Pivot)은 기을 의미하는 개념으로, 피벗보다 작으면 왼쪽, 크면 오른쪽과 같은 방식으로 파티셔닝을 하면서 쪼개 나갑니다.

- 퀵 정렬은 여러가지 변형(variation)이 존재하지만, 이 글에서는 대표 퀵 정렬 알고리즘 하나만 보도록 하겠습니다. 

 

1.1 퀵 정렬의 원리

1) 기준이 되는 데이터를 피벗(Pivot)으로 설정한다.

   : 대표적인 분할 방식인 호어 분할(Hoare Partition)방식을 기준으로 진행

   ( ※ 피벗을 어떻게 설정하고 리스트를 분할하는가에 따라서 다양한 방식의 퀵정렬이 존재)  

2) 피벗을 설정 한 후, 피벗을 기준으로 왼쪽에서는 피벗보다 큰 데이터를 찾고, 오른쪽에서는 피벗보다 작은 데이터를 찾아서 서로 위치를 교환한다.

3) 1,2의 과정을 반복한다.

 

 

<그림으로 이해하는 퀵정렬>

: 아래 그림에서는 마지막 데이터를 첫번째 피벗으로 정하였다.

[출처] https://morioh.com/p/b0deaa623ac4

 

1.2 퀵 정렬 파이썬 코드

1.2.1 가장 직관적인 퀵정렬 코드

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array, start, end):
    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: # 엇갈렸다면 작은 right -=1 데이터와 피벗을 교체
            array[right], array[pivot] = array[pivot], array[right]
            
        else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체 
            array[left], array[right] = array[right], array[left]
            
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right-1)
    quick_sort(array, right+1, end)
    
quick_sort(array, 0, len(array)-1)
print(array)

<설명이 있는 이미지>

 

1.2.2 파이썬의 장점을 살린 코드

- 위에서본 전통적인 퀵정렬 방식 보다는 좀 더 비효율적이지만, 아래 보는바와 같이 매우 깔끔하고 직관적이다

array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]

def quick_sort(array):
    
    #리스트가 하나 이하의 원소만 담고 있다면 종료
    if len(array) <= 1:
        return array
    
    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트 
    
    left_side = [x for x in tail if x <= pivot] #분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] #분할된 오른쪽 부분
    
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))
   
#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

<설명이 있는 이미지>

1.3 퀵 정렬의 시간 복잡도 

- 퀵 정렬의 시간복잡도는 평균 O(Nlog₂N)으로, 앞에서 배운 선택정렬, 삽입정렬보다 매우 빠릅니다. 

- 시간 복잡도 식에대한 증명은 계산이 까다로워서 다루지 않았습니다. 다만, 피벗이 바뀔 때마다 분할이 일어나는데 이떄 정활히 절반으로 쪼개진다는 것을 생각하면 O(Nlog₂N)를 기억하기 훨씬 쉬울 것 같습니다.

 

- 퀵 정렬의 시간 복잡도는 데이터가 무작위로 입력된 경우 빠르게 효율적으로 잘 동작하지만, 이미 정렬이 되어있는 경우 매우 느리게 작동합니다. 퀵정렬의 평균 시간복잡도는 O(Nlog₂N)이지만, 최악의 경우 O(N²)이 될수도 있습니다.  

 

 

 

 

 

- 지금까지 선택 정렬(Selection sort), 삽입 정렬(Insertion sort), 퀵 정렬(Quick sort)에 대해서 알아보았습니다. 세가지 정렬은 모두 데이터를 비교하며 위치를 변경하 하는 유형의 정렬 방법, '비교 기반의 정렬 알고리즘'입니다. 

- 다음 글에서는 비교 기반의 정렬 알고리즘이 아닌 계수 정렬(Count Sort)에 대해서 알아보도록 하겠습니다. 

2021.07.11 - [알고리즘(Algorithm)] - [알고리즘][정렬] ④ 계수 정렬 (Count Sort) - Python

[알고리즘][정렬] ④ 계수 정렬 (Count Sort) - Python

 

 

 

<참고> '이것이 코딩 테스트다 with 파이썬'

http://www.kyobobook.co.kr/product/detailViewKor.laf?mallGb=KOR&ejkGb=KOR&barcode=9791162243077 

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 교보문고

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178&orderClick=LEa&Kc=

파이썬 알고리즘 인터뷰 - 교보문고