Quick Sort

퀵 정렬은 파이썬의 유명한 Package인 Pandas에서 보셨을 수 도 있습니다.

(Pandas DataFrame을 정렬하는 방법중 하나로 쓰입니다)

pandas.pydata.org/pandas-docs/version/0.15.2/generated/pandas.DataFrame.sort.html

pandas.DataFrame.sort — pandas 0.15.2 documentation

퀵 정렬은 분할정복 알고리즘의 일종으로, Pivot 원소를 선정하여 해당 원소를 이동시킨 후 좌우를 분할해서 정렬을 진행합니다.

순서를 보면 아래와 같습니다.

1. 맨 처음 원소를 Pivot원소로 지정.

2. Pivot 원소를 기준으로 

  왼쪽 부분배열의 모든 값 < 피벗 < 오른쪽 부분배열의 모든 값

이 되는 위치에 Pivot 원소를 이동시킨다.

3. 왼쪽배열과 오른쪽 배열에 1~2 과정을 반복한다.

 

중요한건 처음 주어진 배열이 정렬이 되어있지 않기 때문에, 2번 과정을 수행할 때 단순 비교를 통해서 피벗의 위치를 정할수가 없습니다.

 

때문에 퀵 정렬을 진행하기 전에 Pivot 원소를 제외한 나머지 배열에서 Partition이라는 과정을 진행합니다.

Partion의 과정은 다음과 같습니다.

1. Pivot을 제외한 배열에서 가장 왼쪽을 Left, 가장 오른쪽을 Right라고 할 때

And(Left<Pivot?, Right>Pivot?) 여부를 검사한다.

2. And(Left<Pivot?, Right>Pivot?) == True일 경우, Left와 Right 원소의 값을 교환해준다.

3. 이 과정이 Left와 Right의 Index가 교차할때까지 진행한다.

때문에 Partition을 진행하게 되면 정렬이 된것은 아니지만, 특정 위치 기준으로 좌우의 값이 특정 값보다 크거나, 작게 나뉘게 됩니다.

 

퀵 정렬의 경우 이미 정렬된 배열이나, 역순으로 정렬된 배열에서 가장 나쁜 성능을 보여줍니다.

잘 생각해보면, Pivot 원소가 계속 최대값 or 최소값으로 선정되기 때문입니다.

T(n) = T(n-1) + Θ(n)이 되고, 해당 점화식을 풀면

T(n) = O(n2)의 알고리즘 성능을 보여줍니다.

 

반면 잘 섞인 배열(Pivot이 항상 중앙에 위치)에서는 퀵 정렬이 최고의 성능으로 동작하여

T(n) = 2*T(n/2) + Θ(n) 이 되고, 이 점화식을 풀면

T(n) = O(nlogn)의 알고리즘 성능을 보여주는 것을 확인할 수 있습니다.

 

import random
#Generate ordered List
Data = [i for i in range(20)]
#Shuffle ordered list
random.shuffle(Data)

#Quick Sort에 사용할 partition 함수를 정의
def partition(DT_list_part, Max):
    #partition을 진행할 pivot 원소를 선택합니다.
    pivot = DT_list_part[0]
    left = 1
    right = Max-1
    #pivot 원소를 옮기기 위해서, 사전에 pivot원소를 제외한 부분배열을
    #1차적으로 정렬해줍니다(Pivot 원소 기준으로 왼쪽은 작게, 오른쪽은 크게)
    while left<=right:        
        if DT_list_part[left]<pivot and DT_list_part[right]>pivot:
            left = left+1
            right = right-1
        elif DT_list_part[left]>pivot and DT_list_part[right]>pivot:
            right = right-1
        elif DT_list_part[left]<pivot and DT_list_part[right]<pivot:
            left = left+1
        elif DT_list_part[left]>pivot and DT_list_part[right]<pivot:
            temp = DT_list_part[left]
            DT_list_part[left] = DT_list_part[right]
            DT_list_part[right] = temp
    #Pivot 원소가 이동한 Index를 반환해줍니다.
    return right
        

def quick_sort(DT_list):  
    n = len(DT_list)
    #index Error 발생방지
    if n>1:        
    	#사전에 정의된 partition을 이용해서 Pivot을 제외한 부분배열 정렬
        #및 Pivot원소가 이동한 Index를 구합니다.
        change_loc = partition(DT_list, n)    
        #Pivot원소의 이동
        temp = DT_list[0]
        DT_list[0] = DT_list[change_loc]
        DT_list[change_loc] = temp
        #이동한 위치 기준으로 좌우 부분배열을 나누고, 동일한 Quick Sort를 진행합니다.
        DT_list[0:change_loc]= quick_sort(DT_list[0:change_loc])
        DT_list[change_loc+1:] = quick_sort(DT_list[change_loc+1:])
    return DT_list

quick_sort(Data)