[Python3] SWEA 퀵 정렬 5205

문제 :

퀵 정렬을 구현해 N개의 정수를 정렬해 리스트 A에 넣고, A[N//2]에 저장된 값을 출력하는 프로그램을 만드시오.

 

접근 :

퀵 정렬 알고리즘을 적용했다.

 

풀이 :

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    low, equal, high = [], [], []
    for num in arr:
        if num < pivot:
            low.append(num)
        elif num > pivot:
            high.append(num)
        else:
            equal.append(num)
    return quick_sort(low) + equal + quick_sort(high)
    

T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = list(map(int, input().split()))
    ans = quick_sort(arr)
    print(f'#{tc} {ans[N//2]}')

 

사실, 정렬 라이브러리로 훨씬 간편하게 풀 수도 있다.

#정렬 라이브러리
T = int(input())
for tc in range(1, T+1):
    N = int(input())
    arr = sorted(list(map(int, input().split())))
    ans = arr[N//2]
    print(f'#{tc} {ans}')