[누구나 자료구조 알고리즘] python 퀵정렬

💡 Goal
- 퀵정렬 알고리즘을 이해한다.
- 퀵정렬 알고리즘을 파이썬으로 구현한다.
- 퀵정렬 알고리즘 특징을 2가지 이상 말하기.

개념

---

• 다른 원소들과 비교만으로 정렬을 수행하는 비교 정렬
  • 분할 정복 알고리즘중 하나
    • 분할정복이란 → 문제를 2개로 분리하고 해결한 다음 결과를 다시 합치는 전략
• 매우 빠른 속도를 자랑하며 python의 sort가 퀵정렬로 구현됌
• 리스트에 pivot을 지정 후 pivot을 기준으로 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 옮기는 전략
  • 분할 : pivot을 기준으로 2개(좌, 우) 배열로 분할한다
  • 정복 : 분할한 배열들의 크기가 분할이 불가능할때까지 순환 호출 (반복 호출)
  • 결합 : 분할이 불가능할때까지 정렬된 배열들을 하나로 합친다.

순서(오름차순 기준)

---

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

특징

---

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

코드

---

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

    pivot = start
    left = start + 1
    right = end

    while left <= right:
        while left <= end and arr[pivot] >= arr[left]:
            left += 1

        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임을 알 수 있다.