퀵 정렬(Quick Sort)

퀵 정렬(Quick Sort)

• 분할 정복 알고리즘(정복 후 분할)
• 기준 데이터(Pivot)를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법
• 첫 번째 데이터를 기준 데이터(Pivot)로 설정

퀵 정렬 알고리즘 수행과정

퀵 정렬을 수행할 때는 왼쪽에서부터 피벗보다 큰 데이터를 고르고, 오른쪽에서부터 피벗보다 작은 데이터 고름

[Step 0]

• Pivot: 5
• 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택됨
• 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택됨
• 두 데이터의 위치를 서로 변경

[Step 1]

• Pivot: 5
• 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'이 선택됨
• 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택됨
• 두 데이터의 위치를 서로 변경

[Step 2]

• Pivot: 5
• 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택됨
• 오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '1'가 선택됨
• 위치가 엇갈리는 경우 ‘Pviot’과 ‘작은 데이터’의 위치를 서로 변경

[분할 완료]

• ‘5'의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 큼
• 분할(Divide): 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업

[왼쪽 데이터 묶음 정렬]

• 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행

[오른쪽 데이터 묶음 정렬]

• 오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행

퀵 정렬 알고리즘 의사코드

QuickSort(A, left, right)
입력: 배열 A[left]~A[right]
출력: 정렬된 배열 A[left]~A[right]
1. if (left < right) {
2. 	피봇을 A[left]~A[right] 중에서 선택하고,   	
		피봇을 A[left]와 자리를 바꾼 후, 
		피봇과 배열의 각 원소를 비교하여 피봇보다 작은 	숫자들은 A[left]~A[p-1]로 옮기고, 
		피봇보다 큰 숫자들은 A[p+1]~A[right]로 옮기며,
		피봇은 A[p]에 놓는다.
3. 	QuickSort(A, left, p-1)      // 피봇보다 작은 그룹
4. 	QuickSort(A, p+1 right)     // 피봇보다 큰 그룹
      }

• Line 1
  • 배열 A의 가장 왼쪽 원소의 인덱스(left)가 가장 오른쪽 원소의 인덱스(right)보다 작으면 line2~4에서 정렬 수행
  • 만약 그렇지 않으면 1개의 원소를 정렬하는 경우임. 1개의 원소는 이미 정렬되어 있으므로 그대로 호출을 마침.
• Line 2
  • A[left]~A[right]에서 피봇을 선택하고,
  • 배열 A[left+1]~A[right]의 원소들을 피봇과 비교하여,
  • 피봇보다 작은 그룹인 A[left]~A[p-1]과 피봇보다 큰 그룹인 A[p+1]~A[right]로 분할하고
  • A[p]에 피봇을 위치시킨다.
  • 즉, p는 피봇이 위치한 배열 A의 인덱스이다.
• Line 3: 피봇보다 작은 그룹인 A[left]~A[p-1]을 재귀적으로 호출
• Line 4: 피봇보다 큰 그룹인 A[p+1]~A[right]을 재귀적으로 호출

퀵 정렬 알고리즘 코드

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

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        return
    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)

파이썬의 장점을 살린 방식

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

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array

    pivot = array[0] # 피벗은 첫 번째 원소
    tail = array[1:] # 피벗을 제외한 리스트

    left_side = [x for x in tail if x <= pivot] # 분할된 왼쪽 부분
    right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분

    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

시간 복잡도

• 피봇 선택이 좌우함. 너무 크거나 너무 작은 숫자가 선택되면 한 부분으로 치우치는 분할을 야기함
• 최악의 경우: O(n^2)
  • = (n-1)+(n-2)+(n-3)+…+2+1 = n(n-1)/2 = O(n^2)
• 평균의 경우 = 최선의 경우
  • $$O(log_2{n})$$

성능 향상 방법

• 입력의 크기가 매우 클 때, 퀵 정렬의 성능을 더 향상시키기 위해 삽입 정렬을 동시에 사용