[알고리즘] 정렬 : 퀵 정렬

퀵 정렬은 합병 정렬과 같이 분할 정복 알고리즘을 적용한 정렬 기법이며 평균적으로 매우 빠른 속도를 갖고있다. 또한 정렬 대상에 동일한 키 값이 존재할 경우 키 값의 순서가 바뀌는 불안정 정렬이다.

---

개념

• 퀵 정렬은 피벗(pivot)을 설정하여 피벗을 기준으로 작은 값은 피벗의 왼쪽으로 큰 값은 피벗의 오른쪽으로 이동시킨다.
• 아래에 정렬할 대상이 있다. 여기서는 가장 앞에 있는 값을 피벗으로 설정해보자. 

[3, 1, 10, 6, 4, 7, 8, 2, 5, 9]

• 그렇다면 3이 피벗이되고 3을 기준으로 작은 값은 왼쪽으로 큰 값으 오른쪽으로 이동시키면 아래와 같은 결과를 갖는다.

[1, 2] < [3] < [10, 6, 4, 7, 8, 5, 9]

• 위와 같이 분리가 되었다면 왼쪽은 왼쪽끼리 오른쪽은 오른쪽끼리 신경을 쓰면 된다.  이제 3의 왼쪽을 다시 1을 피벗으로 나눈다면 한 개의 숫자들로 만들어지기 때문에 합치기만 하면된다.
• 그리고 3의 오른쪽을 다시 10을 기준으로 아래와 같은 과정을 거치게 된다.

[10, 6, 4, 7, 8, 5, 9]
[6, 4, 7, 8, 5, 9] < [10]

[4, 5] < [6] < [7, 8, 9] < [10]
[4] < [5] < [6] < [7] < [8, 9] < [10]

• 최종적으로 각각의 리스트에 숫자가 한 개가 남았다면 합쳐서 정렬의 결과를 완성시킬 수 있다.
• 병합 정렬은 원소들을 계속해서 반으로 나눈 후에 나눈 것을 합치면서 정렬을 시도하지만 퀵 정렬은 피벗을 기준으로 비교를 통해 정렬한 후에 합치는 과정을 거치게된다.

 

구현

• 먼저 여기서는 pivot을 중간값으로 설정하였다.
• 이제 pivot을 기준으로 작은 값은 왼쪽으로 이동시키고 큰 값은 오른쪽으로 이동시킨다.
• 이제 각각 이동시킨 리스트를 다시 quick_sort() 재귀호출을 통해 위의 과정을 반복한다.
• 리스트에 원소가 하나만 남을 경우 합쳐나간다면 정렬된 결과를 얻을 수 있다.

def quick_sort(numbers):
    if len(numbers) <= 1:
        return numbers

    mid = len(numbers) // 2
    pivot = numbers[mid]
    less_numbers, equal_numbers, greater_numbers = [], [], []
    for i in range(len(numbers)):
        if numbers[i] < pivot:
            less_numbers.append(numbers[i])
        elif numbers[i] > pivot:
            greater_numbers.append(numbers[i])
        else:
            equal_numbers.append(numbers[i])

    return quick_sort(less_numbers) + equal_numbers + quick_sort(greater_numbers)

---

특징

• 평균적으로 속도가 빠르며 O(logN)의 시간복잡도를 갖는다.
• 추가적인 메모리를 필요로하지 않는다.
• 이미 정렬된 리스트에 퀵 정렬을 시도한다면 피벗에 의해 불균형 균형이 일어나 오히려 수행시간이 더 걸리게 된다.
• 따라서 최적의 피벗을 선택하기 위한 방법이 무엇이 있는지 찾아보도록 해야겠다.