algorithm-quick_sort_partition_animation.gif


개념

  • 다른 원소들과 비교만으로 정렬을 수행하는 비교 정렬

    • 분할 정복 알고리즘

      중 하나

      • 분할정복이란 → 문제를 2개로 분리하고 해결한 다음 결과를 다시 합치는 전략

  • 매우 빠른 속도를 자랑하며 python의 sort가 퀵정렬로 구현

  • 리스트에 pivot을 지정 후 pivot을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 옮기는 전략

    • 분할 : pivot을 기준으로 2개(좌, 우) 배열로 분할한다.
    • 정복 : 분할한 배열들의 크기가 분할이 불가능할때까지 순환 호출한다. (반복 호출)
    • 결합 : 분할이 불가능할때까지 정렬된 배열들을 하나로 합친다.

순서(오름차순 기준)

  1. pivot을 임의로 하나를 정한다.
  2. pivot을 제외한 나머지 길이에서 왼쪽은 pivot보다 크거나 같은 수 오른쪽은 작거나 같은 수를 찾는다.
  3. 찾은 데이터를 서로 위치를 변경한다. (swap)
  4. 2,3단계를 반복한다.
  5. 반복하다보면 결국 같은 데이터를 하나 가리키게 되는데 이때 pivot과 위치를 변경한다. (분할)
  6. 분할된 이후 pivot을 기준으로 다시 왼쪽과 오른쪽을 하나의 리스트로 보고 각각 1~3단계를 반복한다.

특징

  • 매우 빠른 정렬 알고리즘
  • 최악(역순 정렬)의 경우 삽입정렬 또는 선택정렬과 성능이 유사하지만 평균시나리오는 훨씬 빠름
  • 분할이란 개념에 기반된 알고리즘

코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

def quick_sort(arr, start, end):
    if start >= end:
        return

    pivot = start
    left = start + 1
    right = end

    while left <= right:  # 오른쪽 수가 더 클때까지 (정렬 완료시)
        # 좌측에서 찾는 반복 (pivot보다 큰 수 찾기)
        while left <= end and arr[pivot] >= arr[left]:
            left += 1

        # 우측에서 찾는 반복 (pivot보다 작은 수 찾기)
        while right > start and arr[pivot] <= arr[right]:
            right -= 1

        if left > right:
            arr[pivot], arr[right] = arr[right], arr[pivot]
        else:
            arr[left], arr[right] = arr[right], arr[left]

    quick_sort(arr, start, right - 1)
    quick_sort(arr, right + 1, end)

시간복잡도

각 분할마다 배열의 원소를 pivot과 비교하기 때문에 최소 n번의 횟수가 발생한다.

N번은 pivot을 지정하고 왼쪽과 오른쪽 포인터가 서로 만나기까지의 횟수를 의미한다.

교환 횟수는 주어진 데이터가 얼마나 정렬되어 있는지에 따라 조금씩 차이가 있으며

최대로는 왼쪽, 오른쪽 포인터별로 회당 교환이 이루어진다 생각했을때 n/2 번이 발생한다.

계속해서 이진탐색처럼 둘로 나뉘게 되면 결국 횟수는 log2n번이 되고 비교에서 발생한 n번과

합쳐서 계산하게 되면 nlog2n임을 알 수 있다.

https://user-images.githubusercontent.com/48043799/145669247-dcbdb429-4b9f-4e3e-8ce0-22fa38f19fcd.png


퀵 셀렉트

무작위로 정렬된 배열이 있을때 어떤 조건에 부합하는 값을 찾을때 사용하는 것을 말한다.

퀵 정렬 후 n번째 요소를 찾아가도 되지만 퀵 셀렉트를 사용하면 더 나은 성능을 발휘한다.

퀵 셀렉트는 분할에 기반하며, 퀵정렬과 이진 탐색의 조합이라고 보면 된다.

예를 들어 8개의 데이터가 있을때 퀵 정렬을 통해 분할을 한다면 pivot이 배열의 중간에 위치한다.

  1. 분할 후 pivot은 n/2 index에 위치
  2. 찾고자 하는 n번째 데이터가 pivot의 위치보다 큰지 작은지에 따라 조건에 맞는 영역을 재탐색

해당 방법을 쓰게 되면 5번째 값을 찾고 싶을때

pivot이 5보다 크다면 왼쪽을 기준으로 찾으면 되기 때문에 매우 효율적임을 알 수 있다.

또한 전체 정렬을 하지 않고서도 데이터를 더 빠르게 찾을 수 있다는 점도 특징이다.

8개의 데이터를 기준으로 분할해가면

  • 8개의 원소를 가진 배열 1개
  • 4개의 원소를 가진 배열 2개
  • 2개의 원소를 가진 배열 2개

로 총 8+4+2로 14단계가 걸린다.

8을 기준으로 볼때 약 2n이 소요되며 이를 시간복잡도로 보면 O(n)임을 확인할 수 있다.