[알고리즘][퀵정렬][QuickSort][정렬][파이썬][Python]-정리 및 코드

Quick Sort(퀵 정렬)

 

퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속합니다.

퀵 정렬은 분할 정복 알고리즘의 하나로, 평균적으로 매우 빠른 수행속도를 보입니다. 

분할 정복 알고리즘을 사용하는 병합 정렬(merge sort)와 다르게 퀵 정렬은 비균등하게 분할합니다.

 

아이디어

 

퀵 정렬은 위에서 언급한대로 분할 정복 알고리즘을 사용한다. 분할 정복은 문제를 작은 2개의 문제로 분리하고 각각을 해결한다음 결과를 모아서 원래의 문제를 해결하는 전략이다. 분할 정복은 일반적으로 재귀 호출을 사용하여 구현한다.

과정은 다음과 같다. 리스트에 있는 요소 하나를 선택한다. 이를 피벗(pivot)이라고 한다. 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로, 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 보낸다. 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다. 분할된 부분 리스트에 대해 재귀 호출을 사용하여 정렬을 반복한다. 부분리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분리스트로 나누는 과정을 반복한다. 

 

알고리즘

퀵 정렬의 알고리즘은 다음과 같습니다. 정렬 되지 않은 무작위의 숫자가 리스트에 저장되어 있고 오름차순으로 정렬을 한다고 가정합니다.

 

예:  [3, 2, 4, 5, 1, 3] (정렬되지 않은 리스트)

 

먼저 피벗을 설정합니다. 피벗 값은 부분 리스트의 첫번째 요소로 설정합니다(여기서는 3). 그리고 빈 리스트를 세 개를 만들어 줍니다. 각 리스트는 피벗보다 작은 요소를 담을 리스트, 피벗과 같은 요소를 담을 리스트, 피벗보다 큰 요소를 담을 리스트 입니다. 이제 부분 리스트의 각 값을 피벗과 비교하여 부분 리스트에 저장합니다. 그 후, 피벗 보다 작은 요소를 저장한 small_list와 피벗 보다 큰 요소를 저장한 big_list를 각각 다시 한번 재귀 호출 합니다. 재귀 호출시 부분 리스트의 길이가 1 이하라면, 더이상 분할 할 요소가 없으므로 부분리스트를 그대로 리턴시켜줍니다. 

 

결과 1. small_list=[2, 1], equal_list=[3, 3], big_list=[4, 5]                pivot : 3

      - small_list와 big_list는 정렬 함수를 재귀 호출.

 

(small_list를 부분 리스트로 정렬 함수 재귀 호출)

결과 1.1. small_list=[1], equal_list=[2], big_list=[]                        pivot : 2

 

(더 이상 정렬할 부분 리스트가 없으므로 small_list, equal_list, big_list 순으로 리스트 병합)

결과 1.2. small_list=[1, 2]

 

(big_list를 부분 리스트로 정렬 함수 재귀 호출)

결과 2.1. small_list=[], equal_list=[4], big_list=[5]                        pivot : 4

 

(더 이상 정렬할 부분 리스트가 없으므로 small_list, equal_list, big_list 순으로 리스트 병합)

결과 2.2. big_list=[5]                          

 

결과 1의 부분 리스트인 small_list, equal_list, big_list가 모두 정렬되었으므로, 모든 부분리스트를 병합

 

 

특징 

장점: 속도가 빠르다( 시간복잡도가 O(nlogn)을 가지는 다른 정렬 알고리즘과 비교해도 가장 빠르다)

       추가 메모리 공간을 필요로 하지 않는다. (퀵 정렬은 O(logn)만큼의 메모리를 필요로 한다.)

 

단점: 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 오래걸린다.

 

퀵 정렬의 불균형 분할을 방지하기 위해 피벗을 선택할때 더욱 리스트를 균등하게 분할 할 수 있는 요소를 선택한다.(ex. 리스트 내 요소중 일부 데이터 중에서 중간 정도 크기의 값을 선택한다)

 

시간 복잡도 Big(O)

 

퀵 정렬은 최선의 경우 O(nlogn)의 시간 복잡도를 가지며, 일반적으로도 O(nlogn)의 시간 복잡도를 갖는다. 하지만 최악의 경우 리스트가 불균형하게 나누어지는 경우(리스트가 이미 정렬된 경우) O(n^2)의 시간 복잡도를 갖는다.

 

 

소스코드

 
unsorted_list=[5,3,8,4,9,1,6,2,7]
 
def quick_sort(arr):
 
    if len(arr)==0:
        return arr
    
    pivot=arr[0]
    small_list=[]
    equal_list=[]
    big_list=[]
 
    for i in range(len(arr)):
        if arr[i]>pivot:
            big_list.append(arr[i])
        elif arr[i]<pivot:
            small_list.append(arr[i])
        else:
            equal_list.append(arr[i])
 
    result=quick_sort(small_list)+equal_list+ quick_sort(big_list)
 
    return result
 
print(quick_sort(unsorted_list))