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

퀵 정렬(Quick Sort)

---

퀵 정렬(Quick Sort) 이란?

퀵 정렬은 평균적으로 매우 빠른 수행속도를 자랑하는 정렬 방법으로 분할정복(Divide and Conquer) 알고리즘이다.

퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다. 또한 병합 정렬과는 다르게 퀵 정렬은 배열을 비 균등하게 분할한다. 

 

 

분할(Divide) → 정복(Conquer) → 결합(Combine)

 

 

퀵 정렬은 pivot 을 선정하여 pivot 을 기준으로 좌측과 우측으로 pivot 보다 작은 값은 왼쪽 pivot 보다 큰 값은 오른쪽으로 재배치를 하고 계속해서 분할하여 정렬하는 알고리즘이다. 

 

 

 

 

 

* 분할정복(Divide and Conquer)

문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략이다.

 

---

퀵 정렬(Quick Sort) 알고리즘의 구체적인 개념

하나의 리스트를 피벗(pivot)을 기준으로 두 개의 비 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트가 되게 하는 방법이다. 

 

퀵 정렬은 다음 단계들로 이루어진다.

• 분할(Divide): 입력 배열을 피벗을 기준으로 비 균등하게 2개의 부분 배열로 분할한다. (왼쪽 - 피벗보다 작은 요소들, 오른쪽 - 피벗보다 큰 요소들)
• 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 방법을 적용한다. 
• 결합(Combine): 정렬된 부분 배열들을 하나의 배열에 합병한다.
• 순환 호출이 한번 진행될 때마다 최소한 하나의 원소(피벗)은 최종적으로 위치가 정해지므로 이 알고리즘은 반드시 끝난다는 걸 보장할 수 있다.

 

---

예제

 

 

---

퀵 정렬(Quick Sort) 시간 복잡도

 

1. 최선의 경우

 

 

 

T(n) = O(nlog n)

 

 

2. 최악의 경우

 

 

T(n) = O(n^2)

 

 

3. 평균

 

T(n) = O(nlogn)

 

 

 

---

퀵 정렬(Quick Sort) 단점

partition() 함수에서 피벗 값이 최소나 최대값으로 지정되어 파티션이 나누어지지 않았을 때, O(n^2)에 대한 시간 복잡도를 가진다.

즉, 정렬하고자 하는 배열이 오름차순 정렬 되어있거나 내림차순 정렬 되어있으면 O(n^2)의 시간 복잡도를 가진다.

 

---

코드(Python)

array =[5,7,9,0,3,1,6,2,4,8]

def quick_sort(array,start,end):
    if start>= end:         # 원소가 1개인 경우 종료
        return
    pivot = start           # pivot 은 첫 번째 원소
    left = start + 1
    right = end
    
    while left<=right:
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while left<=end and array[left]<=array[pivot]:
            left +=1
        while right>start and array[right]>= array[pivot]:
            right-=1
        if left>right:  #엇갈렸다면 작은 데이터와 피벗을 교체
            array[right],array[pivot]= array[pivot],array[right]
        else:           #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
            array[left],array[right]=array[right],array[left]
    #분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 다시 정렬 수행
    quick_sort(array, start,right-1)
    quick_sort(array,right+1,end)

quick_sort(array,0,len(array)-1)
print(array)