5205. [파이썬 S/W 문제해결 구현] 4일차 - 퀵 정렬

T = int(input())
for test_case in range(1, T+1):
    N = int(input())
    arr = list(map(int, input().split()))
    
    def quick_sort(arr, start, end):
        if start >= end:    # start와 end가 같다 = 원소가 1개
            return
        pivot = start
        left = start + 1
        right = end
        
        while left <= right:
            while left <= end and arr[left] <= arr[pivot]:
                left += 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]
        quick_sort(arr, start, right-1)
        quick_sort(arr, right+1, end)
    
    quick_sort(arr, 0, len(arr)-1)
    answer = arr[N//2]

    print(f"#{test_case} {answer}")

퀵 정렬. 병합 정렬보다 더 알고리즘을 몰라서 알고리즘 구현부터 헤맸다. 얘도 진짜 외워야 할 듯...