알고리즘 - Sorting_퀵정렬

Randomized Quicksort에 대해서 알아보자!

랜덤화 퀵소트(Randomized QuickSort)는 표준 퀵소트의 성능을 개선하기 위해 도입된 변형된 알고리즘입니다. 이 방법은 퀵소트에서 피벗을 선택하는 과정을 무작위화하여, 최악의 경우의 시간 복잡도 발생 확률을 줄이는 데 목적이 있습니다.

랜덤화 퀵소트의 작동 원리

기본 퀵소트 알고리즘은 피벗을 배열의 특정 위치(예: 항상 첫 번째 요소, 마지막 요소)에서 선택하며, 이 때문에 배열의 정렬 상태에 따라 성능이 크게 달라질 수 있습니다. 예를 들어, 이미 정렬된 배열에서 항상 첫 번째 요소를 피벗으로 선택하면, 퀵소트의 시간 복잡도는 최악의 경우 O(n^2)에 도달할 수 있습니다.

랜덤화 퀵소트는 이 문제를 해결하기 위해 피벗을 배열 내의 임의의 요소로 선택합니다. 이로써 배열의 특정 부분에 의존하지 않게 되어, 평균적으로 O(nlogn)의 시간 복잡도를 유지할 수 있게 합니다.

import random

def randomized_quick_sort(arr, low, high):
    if low < high:
        # 피벗 인덱스를 무작위로 선택하고 arr[high]와 교환
        pivot_index = random.randint(low, high)
        arr[pivot_index], arr[high] = arr[high], arr[pivot_index]
        
        # 분할 수행
        pi = partition(arr, low, high)
        
        # 재귀 호출
        randomized_quick_sort(arr, low, pi-1)
        randomized_quick_sort(arr, pi+1, high)

def partition(arr, low, high):
    pivot = arr[high]  # 피벗
    i = low - 1
    for j in range(low, high):
        if arr[j] <= pivot:
            i += 1
            arr[i], arr[j] = arr[j], arr[i]
    arr[i+1], arr[high] = arr[high], arr[i+1]
    return i + 1

# 예제 사용
arr = [10, 7, 8, 9, 1, 5]
randomized_quick_sort(arr, 0, len(arr) - 1)
print(arr)