퀵 정렬 (Quick Sort)

퀵 정렬

: 특정 키 값(pivot)을 중심으로 좌측은 pivot보다 작은 수, 우측은 pivot보다 큰 수가 오도록 서로 교환하는 과정을 의미한다. 왼->오 pivot 보다 큰 값을 찾는 A와 오->왼 pivot 보다 작은 값을 찾는 B로 나누어서 A와 B의 위치를 바꾸는 과정을 계속 반복한다. 이처럼 2개의 서브 리스트가 구성되면 첫 번째 리스트부터 앞의 과정을 반복하는 것이다.

 

문제를 여러개로 분리해서 수행한 후, 그 해결 결과 값들을 합쳐서 원래의 문제를 해결하는 분할 정복 방식을 따르고 있다.

 

"분할 정복 기법 + 재귀 알고리즘 = 퀵 정렬 알고리즘"

 

 

출처: https://visualgo.net/en

 

 

 

파이썬으로 구현한 퀵 정렬

from random import randint

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left, mid, right = [], [], []
    for i in arr:
        if i < pivot:
            left.append(i)
        elif i > pivot:
            right.append(i)
        else:
            mid.append(i)
    return quick_sort(left) + mid + quick_sort(right)

arr = [randint(1, 50) for i in range(8)]
print(quick_sort(arr))