[알고리즘] Quick Sort

✅ AI 채팅 링크: https://gemini.google.com/share/2a3012ca0e10

Problem definition: We have an unsorted array: [21, 3, 12, 15, 7, 32, 4, 25, 9, 18]. Let’s sort it using a quick sort algorithm, but this time, you will evaluate how an AI handles it.

• Step 1 (Generate): Ask an AI (ChatGPT, Gemini, etc.) to write a standard Quick Sort algorithm with the pivot selection picking the first element. Document the exact prompt you used and the AI's generated code.
• Step 2 (Analyze & Break): Based on the AI's pivot selection strategy, design an adversarial input array (a specific sequence of numbers) that will force this AI-generated code to degrade to its worst-case Θ($𝑛^2$) time complexity.
  • Requirement: Add a counter variable to the AI's code to count the exact number of recursive calls or comparisons to prove it runs in Θ($𝑛^2$) on your adversarial array.
• Step 3 (Optimize): Prompt the AI again (or manually refactor the code) to implement an optimized Quick Sort that achieves Θ(𝑛𝑙𝑜𝑔𝑛) time complexity even on your adversarial array.
• Step 4 (Report): Briefly explain why the first AI code failed efficiency standards on your adversarial input, and why the optimized version successfully mitigated the issue.

Step1

# AI generation code
def quick_sort(arr):
    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr
    
    # Pivot selection: picking the first element
    pivot = arr[0]
    
    # Partitioning
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    
    # Recursive calls
    return quick_sort(left) + [pivot] + quick_sort(right)

# Example usage:
data = [33, 10, 55, 71, 29, 1, 10, 42]
sorted_data = quick_sort(data)
print(f"Sorted Array: {sorted_data}")

Step2

• input array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
• 카운트 변수 추가

## add counter variables
recursive_call_cnt = 0
comparison_cnt = 0

def quick_sort(arr):
    global recursive_call_cnt, comparison_cnt

    ## count recursive function call
    recursive_call_cnt += 1

    # Base case: arrays with 0 or 1 element are already sorted
    if len(arr) <= 1:
        return arr

    # Pivot selection: picking the first element
    pivot = arr[0]

    # modified Partitioning
    ## modified to add counter variable
    left = []
    right = []

    for x in arr[1:]:
        comparison_cnt += 1  ## count comparison
        if x <= pivot:
            left.append(x)
        else:
            right.append(x)

    # Recursive calls
    return quick_sort(left) + [pivot] + quick_sort(right)

# Example usage:
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
sorted_data = quick_sort(data)
print(f"Original Array: {data}")
print(f"Sorted Array: {sorted_data}")

## check counter variable
print(f"recursive call: {recursive_call_cnt}, comparison: {comparison_cnt}")

참고) 코드 주석 중 ##으로 시작하는 주석은 직접 작성한 것이며, #으로 시작하는 주석은 AI가 생성한 주석입니다.

Step3

import random

def quick_sort(arr):
    def sort(low, high):
        if low >= high:
            return

        # 최적화 포인트: 피벗을 무작위로 선택하여 최악의 케이스 방지
        random_index = random.randint(low, high)
        arr[low], arr[random_index] = arr[random_index], arr[low]
        
        pivot_index = partition(low, high)
        
        # 분할 정복
        sort(low, pivot_index - 1)
        sort(pivot_index + 1, high)

    def partition(low, high):
        pivot = arr[low]
        left = low + 1
        right = high

        while True:
            # 피벗보다 큰 값을 찾을 때까지 left 이동
            while left <= right and arr[left] <= pivot:
                left += 1
            # 피벗보다 작은 값을 찾을 때까지 right 이동
            while left <= right and arr[right] >= pivot:
                right -= 1
            
            if left <= right:
                arr[left], arr[right] = arr[right], arr[left]
            else:
                break
        
        # 피벗을 제 위치(right)로 이동
        arr[low], arr[right] = arr[right], arr[low]
        return right

    sort(0, len(arr) - 1)
    return arr

# 테스트
data = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
print(f"Sorted: {quick_sort(data)}")

Step4

첫 번째 AI 코드는 입력 배열의 상태와 무관하게 항상 첫 번째 원소를 피벗으로 고정한다. 이로 인해 이미 정렬된 배열이 주어질 경우, 분할 과정에서 원소가 0개와 n-1개로 쪼개진다. 결과적으로 총 비교 횟수가 1+2+3+…+n-1 = n(n-1)/2번이 되어 최악의 시간 복잡도인 Θ($𝑛^2$)을 가지게 된다.

반면, 최적화된 버전은 피벗을 무작위로 선택한다. 이 방식은 매 분할마다 최솟값이나 최댓값이 연속으로 피벗으로 뽑힐 확률을 통계적으로 매우 낮춰준다. 결과적으로 배열이 어느 정도 균형 있게 분할될 가능성이 높아져 재귀 호출의 깊이가 $log_2{n}$에 가깝게 유지되며, 최종적으로 전체 시간 복잡도가 Θ(𝑛𝑙𝑜𝑔𝑛)으로 개선된다.