[ SW Expert Academy ] 5205. 퀵정렬

 

1차 시도. [ 10 / 10 ] PASS

너무 유명한 퀵정렬 알고리즘을 이해하고 외우기만 하면 되는 문제였다.

잊지 말기 ~ 😋😉

def partition(a, l, r):
    pivot = a[l]
    i = l + 1
    j = r
    while i <= j:
        while (i <= j and a[i] <= pivot): i += 1
        while (i <= j and a[j] >= pivot): j -= 1
        if i <= j:
            a[i], a[j] = a[j], a[i]
    a[l], a[j] = a[j], a[l]
    return j

def quick_sort(a, l, r):
    if l < r:
        s = partition(a, l, r)
        quick_sort(a, l, s-1)
        quick_sort(a, s+1, r)

if __name__ == '__main__':
    T = int(input())
    for test_case in range(1, T + 1):
        n = int(input())
        a = list(map(int, input().split()))
        quick_sort(a, 0, len(a)-1)

        print("#" + str(test_case), a[n // 2])