퀵 정렬

Python으로 배우는 자료구조와 알고리즘

Miriam Antona

Software engineer

퀵 정렬

분할 정복 원칙 적용
많은 프로그래밍 언어에서 구현
분할 기법
- 피벗
- 피벗보다 작은 항목 -> 왼쪽
- 피벗보다 큰 항목 -> 오른쪽
왼쪽 요소를 재귀적으로 정렬
오른쪽 요소를 재귀적으로 정렬

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식.

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색.

호어 분할

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 두 번째 요소를, 오른쪽 포인터는 마지막 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 세 번째 요소를, 오른쪽 포인터는 마지막 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 세 번째 요소를, 오른쪽 포인터는 다섯 번째 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 세 번째 요소를, 오른쪽 포인터는 다섯 번째 요소를 가리킴. 세 번째와 다섯 번째 요소가 교환될 것을 나타내는 화살표가 있음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 세 번째 요소를, 오른쪽 포인터는 다섯 번째 요소를 가리킴. 세 번째와 다섯 번째 요소가 교환되었음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 네 번째 요소를, 오른쪽 포인터는 다섯 번째 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 모두 네 번째 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 네 번째 요소를, 오른쪽 포인터는 세 번째 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색. 두 개의 포인터가 있으며, 왼쪽 포인터는 네 번째 요소를, 오른쪽 포인터는 세 번째 요소를 가리킴. 첫 번째와 세 번째 요소가 교환될 것을 나타내는 화살표가 있음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 세 번째 요소는 파란색. 첫 번째와 세 번째 요소가 교환되었음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 세 번째 요소는 초록색.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 세 번째 요소는 초록색이고, 처음 두 요소는 목록의 왼쪽 부분을 나타내는 주황색.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색, 두 번째 요소는 주황색, 세 번째 요소는 초록색. 왼쪽 포인터와 오른쪽 포인터 모두 두 번째 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색, 두 번째 요소는 주황색, 세 번째 요소는 초록색. 왼쪽 포인터와 오른쪽 포인터 모두 두 번째 요소를 가리킴. 첫 번째와 두 번째 요소가 교환될 것을 나타내는 화살표가 있음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 파란색, 두 번째 요소는 주황색, 세 번째 요소는 초록색. 왼쪽 포인터와 오른쪽 포인터 모두 두 번째 요소를 가리킴. 첫 번째와 두 번째 요소가 교환되었음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째 요소는 주황색, 두 번째와 세 번째 요소는 초록색.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째 요소 모두 초록색.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째 요소는 초록색. 목록의 오른쪽 부분은 주황색.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째 요소는 초록색. 오른쪽 부분의 첫 번째 요소는 파란색. 왼쪽 포인터는 오른쪽 부분의 두 번째 요소를, 오른쪽 포인터는 마지막 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째 요소는 초록색. 오른쪽 부분의 첫 번째 요소는 파란색. 왼쪽 포인터와 오른쪽 포인터 모두 오른쪽 부분의 두 번째 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째 요소는 초록색. 오른쪽 부분의 첫 번째 요소는 파란색. 왼쪽 포인터는 오른쪽 부분의 첫 번째 요소를, 오른쪽 포인터는 두 번째 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 초록색, 다섯 번째와 여섯 번째 요소는 주황색.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 초록색. 해당 요소는 파란색. 왼쪽 포인터와 오른쪽 포인터 모두 마지막 요소를 가리킴.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 초록색. 해당 요소는 파란색. 왼쪽 포인터와 오른쪽 포인터 모두 마지막 요소를 가리킴. 다섯 번째와 여섯 번째 요소가 교환될 것을 나타내는 화살표가 있음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 첫 번째, 두 번째, 세 번째, 네 번째 요소는 초록색. 해당 요소는 파란색. 왼쪽 포인터와 오른쪽 포인터 모두 마지막 요소를 가리킴. 다섯 번째와 여섯 번째 요소가 교환되었음.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 동작 과정

순서가 없는 숫자 목록의 도식. 모든 요소가 정렬되어 초록색으로 표시됨.

호어 분할
- 피벗보다 큰 값을 찾을 때까지 왼쪽 포인터 이동
- 피벗보다 작은 값을 찾을 때까지 오른쪽 포인터 이동

퀵 정렬 - 구현

def quicksort(my_list, first_index, last_index):

    if first_index < last_index:

        partition_index = partition(my_list, first_index, last_index)

        quicksort(my_list, first_index, partition_index)

        quicksort(my_list, partition_index + 1, last_index)

퀵 정렬 - 구현

def partition(my_list, first_index, last_index):

    pivot = my_list[first_index]
    left_pointer = first_index + 1
    right_pointer = last_index

    while True: 
        while my_list[left_pointer] < pivot and left_pointer < last_index:
            left_pointer += 1

        while my_list[right_pointer] > pivot and right_pointer >= first_index:
            right_pointer -= 1

        if left_pointer >= right_pointer:
            break

        my_list[left_pointer], my_list[right_pointer] = my_list[right_pointer], my_list[left_pointer]

    my_list[first_index], my_list[right_pointer] = my_list[right_pointer], my_list[first_index]

    return right_pointer

퀵 정렬 - 구현

my_list = [6, 2, 9, 7, 4, 8] 
quicksort(my_list, 0, len(my_list) - 1)
print(my_list)

[2, 4, 6, 7, 8, 9]

퀵 정렬 - 복잡도

최악의 경우: $O(n^2)$
매우 효율적!
- 평균의 경우: $\Theta(n\log{}n)$
- 최선의 경우: $\Omega(n\log{}n)$
공간 복잡도: $O(n\log{}n)$

연습해 봅시다!

Python으로 배우는 자료구조와 알고리즘