[자료구조 및 알고리즘] 퀵정렬 (Quick Sort)

퀵정렬

 

가장 많이 사용되는 정렬 알고리즘 중 하나. 퀵정렬과 병합정렬 알고리즘은 대부분의 프로그래밍 언어에서 정렬 라이브러리의 근간이 된다.

 

퀵정렬 Idea

 

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸면 어떨까?

 

퀵정렬은 기준(Pivot, 피벗)을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

 

피벗을 설정하고 리스트를 분할하는 방법에 따라 퀵정렬을 구분하는데, 여기서는 호어방식을 다룰 것이다.

 

호어방식

 

리스트에서 첫 번째 데이터를 피벗으로 정한다.

 

피벗 설정 후 왼쪽에서는 피벗보다 큰 데이터를, 오른쪽에서는 피벗보다 작은 데이터를 찾고 교환한다. 이 과정을 반복하면 정렬이 수행된다.

 

특정 리스트에서 피벗을 설정하여 정렬을 수행한 후에 피버을 기준으로 왼쪽 리스트와 오른쪽 리스트에서 다시 정렬을 수행한다.

 

재귀함수로 작성시 구현이 쉽다.

 

퀵정렬이 끝나는 순간: 리스트의 원소가 1개 이하일 때

 

코드1

# 전통 퀵정렬 코드

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

def quick_sort(array, start, end):
    if start >= end: return # 원소가 1개인 경우 종료

    pivot = start
    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) # [0,1,2,3,4,5,6,7,8,9]

 

파이썬의 장점을 살린 코드2

# 파이썬의 장점을 이용한 코드, 비교 연산 횟수가 증가해 시간 면에서는 조금 비효율적이지만, 코드가 직관적이라서 기억하기는 쉽다

def quick_sort_for_python(chaos):
    if len(chaos) <= 1: return chaos

    pivot = chaos[0]
    tail = chaos[1:]

    left_side = [x for x in tail if x <= pivot]
    right_side = [x for x in tail if x > pivot]

    return quick_sort_for_python(left_side) + [pivot] + quick_sort_for_python(right_side)

print(quick_sort_for_python(array))

 

시간복잡도

 

최선의 경우: Ω(Nlog(N))

 

최악의 경우(데이터가 거의 정렬 되어 있을 때, 피벗 값이 최소에 가까울 때) : O(N^2)