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

❗퀵 정렬

• 퀵 정렬 역시 분할정복(Divide and Conquer) 기법을 사용한다. 피벗(Pivot)이란 개념의 기준값을 활용해 피벗보다 작은 값은 왼쪽에, 피벗보다 큰 값은 오른쪽에 배치한다.
• 피벗을 어떤 값을 기준으로 하냐에 따라 성능이 달라지니 잘 봐야 한다.
  ★어떤 값을 피벗으로 두냐에 따라 성능은 다르지만 이번에는 배열의 맨 첫 번째 값을 피벗으로 두고 해보려고 한다.

1) 피벗 선택

• 배열에서 하나의 원소를 선택한다. 이것을 피벗(Pivot)이라 한다.

2) 분할 과정

• 피벗을 제외한 나머지의 정렬이 이루어져야 하므로 인덱스 1부터 마지막 인덱스까지 이동하면서 피벗보다 작은 값은 왼쪽에 두고, 피벗보다 큰 값은 오른쪽에 둔다.
  ※피벗과 같거나 작은 값은 왼쪽에 추가해도 무방하다.

3) 결합 과정

• 왼쪽 리스트 + [Pivot] + 오른쪽 리스트를 결합한 리스트를 반환한다.

4) 재귀 호출

• 왼쪽 리스트와 오른쪽 리스트의 원소가 2개 미만이 될 때까지 즉, 원소가 한 개가 될 때까지 같은 과정을 반복한다.

import sys
input = sys.stdin.readline

def QuickSort(arr, start, end):
    # 원소가 한 개인 경우 종료
    if start >= end:
        return
    # 피벗값을 배열의 맨 처음 원소로 설정
    pivot = start
    left = start + 1
    right = end
    # 왼쪽 인덱스가 오른쪽 인덱스보다 작으면 계속 진행(넘어서면 종료)
    while left <= right:
        # 피벗보다 큰 데이터를 배열의 인덱스 범위 내에서 찾는다.
        # 배열의 왼쪽 인덱스값 1증가
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
        # 피벗보다 작은 데이터를 배열의 인덱스 범위 내에서 찾는다.
        # 배열의 오른쪽 인덱스값 1감소
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
        # 인덱스 값이 엇갈렸다면?
        # 피벗값과 오른쪽 인덱스 값 교체
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        # 인덱스 값이 엇갈리지 않았다면?
        # 왼쪽, 오른쪽 인덱스 값 교체
        else:
            arr[left], arr[right] = arr[right], arr[left]
    QuickSort(arr, start, right-1)
    QuickSort(arr, right+1, end)

arr = [8,9,3,1,2,5,7,10]
print("Before Sort: ", end=" ")
print(arr)
QuickSort(arr, 0, len(arr)-1)
print("After Sort: ", end=" ")
print(arr)