[swea] 5205. 퀵정렬 / python 파이썬

💡 How Quicksort Works ?

퀵정렬은 피봇(pivot)을 기준으로 큰 숫자와 작은 숫자를 서로 교환한 다음 배열을 반으로 나눈다.

즉, 피봇보다 작은 숫자는 피봇 왼쪽으로, 큰 숫자는 오른쪽으로 분할한다.

이런식으로 쭉 내려가면 정렬이 되고, 이를 결합하면 정렬된 리스트를 얻을 수 있다.

👍 분할 정복 알고리즘으로 평균적으로 매우 빠른 수행 속도를 나타내는 것이 특징이다.

 

 

코드

def quick_sort(left, right):
    if left >= right:
        return

    pivot = left
    i = left+1
    j = right-1
    while i <= j:
        while i <= j and a[pivot] >= a[i]:
            i += 1
        while i <= j and a[pivot] <= a[j]:
            j -= 1

        if i <= j:
            a[i], a[j] = a[j], a[i]

    a[pivot], a[j] = a[j], a[pivot]

    quick_sort(left, j)
    quick_sort(j+1, right)


T = int(input())
for tc in range(1, T + 1):
    N = int(input())
    a = list(map(int, input().split()))

    quick_sort(0, len(a))
    print("#{} {}".format(tc, a[N//2]))