[알고리즘] 퀵 정렬에 대해 알아보자! (+Python 구현)

본 포스팅에서는 퀵 정렬(Quick sort) 알고리즘에 대해 알봅니다.

📚 목차

1.  퀵 정렬이란?
2.  퀵 정렬의 동작 과정
3.  퀵 정렬 구현(Python)
4.  퀵 정렬의 시간 복잡도

1.  퀵 정렬이란?

퀵 정렬은 피벗(pivot)이라는 기준 데이터를 설정하고 그 기준 데이터보다 큰 데이터와 작은 데이터의 위치를 변경하는 정렬 방식입니다. 퀵 정렬은 데이터 간의 비교만으로 정렬을 수행하는 비교 정렬 중 하나로서 이름에서 알 수 있듯이 정렬이 빠르다는 특징이 있습니다. 퀵 정렬의 방식은 피벗을 설정하고 데이터를 분할하는 방법에 따라 여러 가지로 구분할 수 있지만, 이번 포스팅에서는 가장 대표적인 분할 방식인 호어 분할(Hoare Partition)을 기준으로 설명드리도록 하겠습니다.

2.  퀵 정렬의 동작 과정

이제 퀵 정렬의 구체적인 동작 과정을 알아보도록 하겠습니다. 호어 분할 방식에서는 "리스트 내 첫 번째 데이터를 피벗으로 설정한다"와 같은 규칙에 따라 피벗을 선정합니다. 피벗 선정 후 아래와 같은 순서로 데이터를 정렬합니다.

 

1️⃣ 리스트 좌측에서 우측 방향으로 피벗보다 큰 데이터를 찾고, 리스트 우측에서 좌측 방향으로 피벗보다 작은 데이터를 찾습니다.

2️⃣ 큰 데이터와 작은 데이터의 위치를 서로 교환합니다.

3️⃣ 찾은 데이터의 위치에서부터 다시 조건에 맞는 데이터를 찾고 위치를 서로 변경해 주는 과정을 반복합니다.

 

그림 1 과 같이 정수 10개가 무작위로 배치되어 있을 때 퀵 정렬을 활용해서 오름차순으로 정렬해 보도록 하겠습니다.

 

그림 1. 정렬되지 않고 무작위로 나열된 0부터 9까지의 정수 10개

 

퀵 정렬 동작 과정은 크게 3가지 파트로 나눌 수 있으며 파트별로 설명드리도록 하겠습니다.

 

1.  분할(Partition): 퀵 정렬을 통해 전체 리스트를 피벗보다 작은 리스트와 피벗보다 큰 리스트로 분할
2.  분할된 좌측 리스트의 퀵 정렬: 피벗보다 작은 리스트 내 퀵 정렬
3.  분할된 우측 리스트의 퀵 정렬: 피벗보다 큰 리스트 내 퀵 정렬

편의상 피벗을 파란색으로, 피벗을 기준으로 크거나 작은 데이터는 회색으로 표현하겠습니다.

(1) 분할

1) 전체 리스트 내 첫 번째 데이터인 5를 피벗으로 설정합니다. 이제 리스트 좌측에서 우측으로 피벗보다 큰 데이터인 8을 찾고, 리스트 우측에서 좌측으로 피벗보다 작은 데이터인 3을 찾습니다. 찾은 데이터의 위치를 서로 변경해 줍니다.

 

2) 데이터가 변경된 위치에서 다시 피벗을 기준으로 데이터를 찾습니다. 이렇게 찾은 9와 4의 위치를 변경해 줍니다.

 

 

3) 데이터가 변경된 위치에서 다시 피벗을 기준으로 데이터를 찾습니다. 이렇게 찾은 6과 2의 위치를 변경해 줍니다.

 

4) 데이터가 변경된 위치에서 다시 피벗을 기준으로 데이터를 찾습니다. 아래 그림과 같이, 이번에는 좌측에서 우측 방향으로 찾은 데이터와 우측에서 좌측 방향으로 찾은 데이터 간의 위치가 서로 엇갈린 것을 확인하실 수 있습니다. 이럴 때는 피벗보다 작은 데이터와 피벗의 위치를 서로 변경해 줍니다. 즉, 피벗보다 작은 데이터 1과 피벗 5의 위치를 서로 변경하여 분할을 수행합니다.

 

 

5) 아래 그림과 같이 리스트가 두 부분으로 분할된 것을 확인하실 수 있습니다. 즉, 피벗 5를 기준으로 좌측 리스트에는 모두 피벗보다 작은 데이터로 구성되어 있으며, 우측 리스트에는 모두 피벗보다 큰 데이터가 구성되어 있습니다.

위 상태에서 좌측과 우측 리스트 각각에 대해 동일한 방식으로 퀵 정렬을 수행하면 전체 리스트에 대해서도 정렬될 것입니다.

왜냐하면 좌측 리스트는 어떻게 정렬해도 반드시 초기 피벗인 5보다 작으며, 우측 리스트는 어떻게 정렬해도 반드시 5보다 크기 때문입니다.

그럼 이제 좌/우측 리스트에 대해 각각 퀵 정렬을 수행하도록 하겠습니다.

(2) 좌측 리스트의 퀵 정렬

먼저 분할 단계의 피벗보다 작은 값들로 구성되어 있는 좌측 리스트를 퀵 정렬을 활용해 정렬하겠습니다.

 

1) 맨 앞의 값인 1을 피벗으로 설정합니다. 

 

2) 좌측에서 우측방향으로 피벗보다 큰 값인 3을 찾고, 우측에서 좌측방향으로 피벗보다 작은 값인 0을 찾았습니다. 두 데이터의 위치를 서로 변경합니다.

3) 데이터가 변경된 위치에서 다시 피벗을 기준으로 데이터를 찾습니다. 아래 그림과 같이, 좌측에서 우측 방향으로 찾은 데이터 3과 우측에서 좌측 방향으로 찾은 데이터 0 간의 위치가 서로 엇갈린 것을 확인하실 수 있습니다. 이럴 때는 피벗보다 작은 데이터와 피벗의 위치를 서로 변경해 줍니다. 즉, 피벗보다 작은 데이터 0과 피벗 1의 위치를 서로 변경하여 분할을 수행합니다.

4) 아래 그림과 같이 리스트가 두 부분으로 분할된 것을 확인하실 수 있습니다. 즉, 피벗 1을 기준으로 좌측 리스트에는 피벗보다 작은 데이터(0)로 구성되어 있으며, 우측 리스트에는 모두 피벗보다 큰 데이터가 구성되어 있습니다.

 

5) 이제 다시 좌측/우측 리스트에 대하여 각각 퀵 정렬을 수행합니다. 좌측 리스트는 데이터가 1개로 이미 정렬이 완료되었다고 가정할 수 있으며 추가적인 분할은 불가능합니다. 우측 리스트에 대해 퀵 정렬을 수행하면 맨 앞에 있는 3이 피벗으로 설정됩니다. 좌측에서 우측 방향으로 피벗보다 큰 값인 4와 우측부터 좌측  방향으로 피벗보다 작은 값인 2를 찾았습니다. 두 데이터의 위치를 서로 변경해 줍니다.

 

6) 이제 좌측에서 우측 방향으로 찾은 데이터 4와 우측에서 좌측 방향으로 찾은 데이터 2 간의 위치가 서로 엇갈린 것을 확인하실 수 있습니다. 분할을 위해 피벗보다 작은 값인 2를 현재 피벗인 3과 위치를 변경합니다.

7) 다시 피벗 3을 기준으로 좌측과 우측 리스트를 정렬하려 했더니 리스트별로 데이터가 1개씩만 남아 있습니다. 분할이 끝나면 좌측 및 우측 리스트는 어떻게 정렬하여도 각각 피벗보다 작거나 큰 값으로만 구성된다고 말씀드렸습니다. 따라서 리스트별로 데이터가 1개씩만 남았기 때문에 이 값들은 모두 정렬이 완료되어 있다는 것을 확인하실 수 있습니다.

(3) 우측 리스트의 퀵 정렬

이제 첫 분할 단계의 피벗보다 큰 값들로 구성되어 있는 우측 리스트를 퀵 정렬을 활용해 정렬하겠습니다.

 

1) 맨 앞의 값인 6을 피벗으로 설정합니다. 

2) 좌측에서 우측 방향으로 피벗인 6보다 큰 값인 9를 찾았습니다. 하지만 우측에서 좌측 방향으로 피벗보다 작은 값은 찾지 못 했습니다. 따라서 앞서 찾은 9와 가장 우측에 있는 8의 위치를 서로 변경합니다.

 

 

3) 데이터가 변경된 각 위치에서 다시 좌측과 우측 방향으로 피벗보다 작거나 큰 값을 찾으면, 피벗인 6보다 큰 값인 8을 찾았지만 피벗보다 작은 값은 찾지 못 했습니다. 따라서 8과 7의 위치를 서로 변경합니다.

 

4) 앞서 좌측 리스트의 퀵 정렬 결과와 병합하면 아래와 같으며 오름차순으로 정렬이 올바르게 된 것을 확인하실 수 있습니다.

3.  퀵 정렬의 구현(+Python)

앞서 살펴본 퀵 정렬의 예시를 실제로 파이썬을 통해 구현해 보겠습니다. 퀵 정렬은 피벗을 설정하고 피벗을 기준으로 좌측 리스트와 우측 리스트로 분할한 후 리스트별로 다시 퀵 정렬을 수행하여 동작합니다. 이러한 동작 원리는 재귀 함수의 원리와 같아 재귀 함수를 활용하면 소스코드를 간결하게 작성하실 수 있습니다. 재귀 함수를 활용할 때는 반드시 종료 조건이 있어야 합니다. 종료 조건은 특정 리스트가 모두 정렬된 상태일 때로, 리스트 내 데이터의 개수가 1개인 경우입니다. 이러한 동작 원리는 아래 소스코드를 통해 더욱 직관적으로 이해하실 수 있을 거라 생각합니다. 소스 코드는 크게 2가지 종류가 있습니다. 일반적으로 널리 쓰이는 코드와 파이썬의 장점을 최대한 활용하여 작성한 소스코드가 있습니다.

(1) 일반적인 코드

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

def quick_sort (arr, start, end):
    # 원소가 1개인 경우 함수 종료
    if start >= end: 
        return
    # 첫 번째 원소를 피벗으로 설정
    pv = start
    # 좌측 리스트 시작점
    left = start + 1
    # 우측 리스트 시작점
    right = end
    
    while left <= right:
    
      # 피벗보다 큰 값을 찾을 때까지 무한 반복문
        while left <= end and arr[left] <= arr[pv]:
            left += 1 

      # 피벗보다 작은 값을 찾을 때까지 문한 반복문
        while right > start and arr[right] >= arr[pv]:
            right -= 1

      # 탐색하는 데이터 위치가 다른 경우(엇갈린 경우)
        if left > right:
            arr[right], arr[pv] = arr[pv], arr[right]
        else:
            arr[left], arr[right] = arr[right], arr[left]
    # 분할 이후 좌측 및 우측 리스트 각각에에 대해 퀵 정렬 수행
    quick_sort(arr, 0, right -1)
    quick_sort(arr, right + 1, end) 

quick_sort(arr, 0, len(arr)-1)
print(arr)

출력 결과

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

위와 같이 10개의 정수가 오름차순으로 정렬되어 출력되는 것을 확인하실 수 있습니다.

(2) 파이썬 장점을 활용한 코드

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

def quick_sort (arr):
    # 리스트 내 원소가 1개인 경우 함수 종료
    if len(arr) <= 1: 
        return arr

    # 첫 번째 원소를 피벗으로 설정
    pv = arr[0]
    # 피벗을 제외한 리스트
    tail = arr[1:]
    
    # 분할된 좌측 리스트
    left_list = [x for x in tail if x <= pv]
    # 분할된 우측 리스트
    right_list = [x for x in tail if x > pv]
    
    # 분할 이후 좌측 및 우측 리스트 각각에에 대해 퀵 정렬 수행
    return quick_sort(left_list) + [pv] + quick_sort(right_list)
    
print(quick_sort(arr))

앞서 살펴본 일반적인 코드에 비해 피벗과 값을 비교하는 비교 연산 횟수가 증가하기 때문에 시간 복잡도 측면에서는 다소 비효율적입니다. 그럼에도 동작 원리를 이해하는 데 더욱 직관적이기 때문에 코드를 기억하는 데에는 더욱 효과적이라고 생각합니다.

출력 결과

0, 1, 2, 3, 4, 5, 6, 7, 8, 9

위와 같이 10개의 정수가 오름차순으로 정렬되어 출력되는 것을 확인하실 수 있습니다.

4.  퀵 정렬의 시간 복잡도

선택 정렬과 삽입 정렬의 시간 복잡도가 최악의 경우에는 O(N^2) 입니다. 이에 비해 퀵 정렬의 시간 복잡도는 O(N * logN) 으로 이름에서부터 알 수 있듯이 정렬 속도가 매우 빠른 편입니다. 그럼에도 리스트가 어느 정도 정렬되어 있는 상태라면 삽입 정렬이 매우 빠르게 동작하는 것에 비해 퀵 정렬은 매우 느리게 동작하는 예외가 있습니다. 따라서 이러한 경우에는 퀵 정렬보다는 삽입 정렬을 활용해 문제를 접근하시는 게 효율적이라는 것을 강조해 말씀드립니다.

참고할만한 포스팅

1.  [알고리즘] 선택 정렬에 대해 알아보자! (+Python 구현)
2.  [알고리즘] 삽입 정렬에 대해 알아보자! (+Python 구현)
3.  [알고리즘] 퀵 정렬에 대해 알아보자! (+Python 구현)
4.  [알고리즘] 계수 정렬에 대해 알아보자! (+Python 구현)
5.  [파이썬] 내장 함수를 활용한 데이터 정렬하기! (sorted, sort 함수)

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.