[알고리즘] Quick Sort

Quick sort

퀵 소트는 분할정복을 이용한 정렬방식 중 하나로 이름처럼 빠른 정렬입니다. 퀵 소트의 방식은 이렇습니다.

1. 무작위로 기준이 되는 수(pivot)를 고릅니다.

2. 이 때 피벗보다 작은 수를 왼쪽으로 놓습니다.

3. 피벗보다 큰 수를 오른쪽에 놓습니다.

4. 왼쪽과 오른쪽에 놓인 각각의 배열을 다시 1번 과정부터 반복합니다.

 

다음 아래와 같은 그림으로 보면

 

이처럼 pivot은 정렬된 것으로 보고 피벗을 기준으로 나머지를 분할하여 다시 피벗을 구해 마지막 피벗하나를 구할때까지 반복하는 구조입니다.

 

 

그렇다면 시간 복잡도 어떠할까요? 

 

일반적인 경우의 시간복잡도는 NlogN을 가집니다.

 

왜냐하면 실제 N개의 수가 있다고 합시다. 만약 피벗이 정말 잘 골라져서 N이 딱 절반씩 계속해서 나눠진다고 보면 다음과 같은 완전이진트리가 됩니다.

 

믿기지않겠지만 이진트리입니다.

 

따라서 높이는 logN만큼 분할하고 각 수에 대해 피벗화해야하므로 N번 피벗을 결정합니다. 즉 N번 피벗화, logN번 분할해서 NlogN을 가지게 됩니다. 하지만 만약 피벗이 적절치 못해 한쪽 방향으로 치우친다면

와 같고 높이가 N이고 N개 원소를 피벗화하므로 이므로 N^2의 시간복잡도를 가지게됩니다.

이런 경우는 거의 정렬된 배열을 퀵 소트로 정렬할 때 나타날 수 있습니다. 

따라서 이런 경우가 생기지 않게 피벗을 랜덤하게 선정하는 것이 효율적이라고 할 수 있습니다. 

 

 

다음은 파이썬 코드입니다.

 

def quick_sort(list):
    if len(list) > 1:
        pivot = list[0]

        left,mid,right = [], [], []

        for num in list[1:]:
            if num > pivot:
                left.append(num)
            elif num < pivot:
                right.append(num)
            else:
                mid.append(num)

        mid.append(pivot)

        return quick_sort(left)+mid+quick_sort(right)
    else:
        return list

if __name__=="__main__":
    numbers = [9,2,5,3,6,1,4,7,10,8]
    print(quick_sort(numbers))

 

출력

 

 

위 코드는 위에 나타난 재귀적인 방법을 파이썬으로 간단히 나타낸 코드입니다.

 

하지만 실제 원시적인 코드는 저장공간을 따로 두지않고 피벗을 기준으로 서로 위치를 변경하며 반복합니다.

한마디로

1. 무작위로 기준이 되는 수(pivot)를 고릅니다.

2. 이 때 피벗보다 작은 수를 왼쪽으로 놓습니다.

3. 피벗보다 큰 수를 오른쪽에 놓습니다.

4. 왼쪽과 오른쪽에 놓인 각각의 배열을 다시 1번 과정부터 반복합니다.

 

위 과정에서 2,3번을 각각 선택한 뒤 피벗을 기준으로 위치를 바꾸는 겁니다.

이 과정을 포함한 코드는 다음과 같습니다.

 

def quick_sort(list,start,end):

    if start >= end:
        return

    pivot = list[start]
    left = start + 1
    right = end

    while left <= right:
        while left <= end and list[left] <= pivot:
            left += 1

        while list[right] >= pivot and right > start:
            right -= 1

        if left > right:
            list[right], list[start] = list[start],list[right]
        else:
            list[left], list[right] = list[right],list[left]

    quick_sort(list,start,right-1)
    quick_sort(list,right+1,end)




if __name__=="__main__":
    numbers = [9,2,5,3,6,1,4,7,10,8]
    quick_sort(numbers,0,len(numbers)-1)
    print(numbers)