[알고리즘] 퀵 정렬(Quick Sort)

퀵정렬이란?​

퀵정렬(Quick Sort)은 퀵이라는 이름답게 평균 속도 O(N*logN)을 자랑하는 매우 빠른 정렬 알고리즘이다.

퀵정렬은 분할정복(Divide & Conquer) 알고리즘의 하나로, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속하는 알고리즘이다.

 

퀵정렬의 전체적인 정렬 과정​

퀵정렬은 임의의 pivot 값을 기준으로

pivot 의 좌측에는 pivot 보다 작은값을 두고

우측에는 pivot 보다 큰 값을 두는 방식으로 정렬을 진행한다.

 

전체적인 정렬 과정은 다음과 같다.

1. 리스트 안의 임의의 요소 하나를 선택한다. 이를 피봇(pivot) 이라고 하자.

2. pivot을 기준으로 pivot의 왼쪽에는 pivot보다 작은 원소를, pivot의 오른쪽에는 pivot보다 큰 원소를 배치한다.

3. pivot을 기준으로 분할된 왼쪽 리스트와 오른쪽 리스트에 대해 다시 1,2의 과정을 반복한다.

4. 이렇게 순환 과정을 통해 분할된 각 리스트의 크기가 0이나 1이 되면 수행을 종료한다.

 

​퀵정렬의 자세한 정렬과정

이를 그림과 함께 좀 더 자세한 과정으로 살펴보자.

1. 피봇을 선택한다.

2. left는 왼쪽에서 오른쪽으로 가면서 피봇보다 큰 수를 찾는다.

3. right는 오른쪽에서 왼쪽으로 가면서 피봇보다 작은 수를 찾는다.

4. 찾은 지점에서 left와 right를 교환한다.

5. 위의 2,3,4과정 left와 right가 교차할 때 까지 반복한다.

6. left와 right가 교차하면 피봇(pivot)과 right를 교환한다.

7. 이렇게 되면 피봇의 왼쪽에는 피봇보다 작은수가, 피봇의 오른쪽에는 피봇보다 큰 수가 위치한다.

8. 피봇을 기준으로 왼쪽과 오른쪽 리스트 두개로 나눠 위의 과정을 반복 수행한다.

9. 이렇게 순환 과정을 통해 분할된 리스트의 크기가 0이나 1이 되면 수행을 종료한다.

 

퀵 정렬의 구현 코드​

• Python 코드

def partition(arr, start, end):
    pivot = arr[start]
    left = start + 1
    right = end
    done = False
    while not done:
        while left <= right and arr[left] <= pivot:
            left += 1
        while left <= right and pivot <= arr[right]:
            right -= 1
        if right < left:
            done = True
        else:
            arr[left], arr[right] = arr[right], arr[left]
    arr[start], arr[right] = arr[right], arr[start]
    return right


def quick_sort(arr, start, end):
    if start < end:
        pivot = partition(arr, start, end)
        quick_sort(arr, start, pivot - 1)
        quick_sort(arr, pivot + 1, end)
    return arr

 

퀵 정렬의 장점 및 단점​

• 장점
  • 속도가 빠르다 (평균 속도가 O(NlogN) 이며 O(NlogN)의 속도를 가지는 다른 정렬 알고리즘과 비교했을 때도 가장 빠르다.)
  • 추가 메모리 공간이 필요하지 않다 (O(logN) 만큼의 메모리를 필요로 한다.)
• 단점
  • 최악의 경우 시간 복잡도는 O(N^2) 이다.

 

면접에 나올 수 있는 질문​

• 퀵 정렬이 최악의 시간복잡도를 가지는 경우를 제시해보세요.
• 퀵 정렬의 소스코드에서 단 두 부분만을 바꿔 내림차순으로 바꿔보세요.

 

참고자료​

• 위키백과 - 퀵정렬
• 안경잡이개발자님 블로그 - 퀵정렬