[알고리즘] 퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

퀵 정렬은 분할 정복 알고리즘의 하나로 평균적으로 매우 빠른 수행 속도를 자랑하는 정렬 알고리즘이다. 합병 정렬(Merge Sort)과 달리 퀵 정렬은 리스트를 비균등하게 분할한다.

퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교정렬에 속한다. 하나의 리스트를 피벗(pivot)을 기준으로 피벗보다 작은 데이터와 큰 데이터를 두 개의 부분 리스트로 나눈 다음, 각 부분 리스트에 대해 다시 재귀적으로 수행하여 정렬하는 방법이다.

 

 

정렬 과정

1. 배열 가운데서 하나의 원소를 선택(→ 이 원소가 피벗)
2. 피벗을 기준으로 피벗보다 작은 원소들은 피벗 앞(왼쪽)으로 오고,
   피벗보다 큰 원소들은 피벗 뒤(오른쪽)로 이동
3. 피벗을 제외하고 나뉘게 된 두 배열은 앞 과정을 더 이상 분할이 불가능할 때(리스트의 크기가 0이나 1이 될 경우)까지 재귀적으로 수행

출처 : https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

 

 

파이썬 코드

def quick_sort(arr):
    if len(arr) <= 1:  # 더이상 분할 불가
        return arr

    pivot = arr.pop(0)  # 기준(피벗)을 첫번째 데이터로 함
    left, right = [], []

    for data in arr:
        if pivot > data:
            left.append(data)
        else:
            right.append(data)
    
    return quick_sort(left) + [pivot] + quick_sort(right)

혹은

def quick_sort(arr):
    if len(arr) <= 1:  # 더이상 분할 불가
        return arr

    pivot = arr[0]  # 기준(피벗)을 첫번째 데이터로 함

    left = [data for data in arr[1:] if pivot > data]
    right = [data for data in arr[1:] if pivot <= data]

    return quick_sort(left) + [pivot] + quick_sort(right)

 

 

 

 

 

https://st-lab.tistory.com/250

자바 [JAVA] - 퀵 정렬 (Quick Sort)

https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html

[알고리즘] 퀵 정렬(quick sort)이란 - Heee's Development Blog

https://gyoogle.dev/blog/algorithm/Quick%20Sort.html

퀵 정렬(Quick Sort) | 👨🏻‍💻 Tech Interview