[SWEA][D3][#11892] 분할정복_퀵정렬

출처

• SW Expert Academy

학습용 포스트입니다. 본 포스트가 문제가 될 시 수정 또는 삭제하겠습니다.

문제

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

입력

첫 줄에 테스트케이스의 수 T가 주어진다. 1<=T<=50

다음 줄부터 테스트 케이스의 별로 정수의 개수 N이 주어지고, 다음 줄에 N개의 정수 ai가 주어진다.

5<=N<=1,000,000, 0 <= ai <= 1,000,000

출력

각 줄마다 “#T” (T는 테스트 케이스 번호)를 출력한 뒤, , N/2번 원소를 출력한다.

예제

입력

3
5
2 2 1 1 3
10
7 5 4 1 2 10 3 6 9 8
100
158 56 163 106 108 153 159 147 93 140 126 9 145 166 191 106 48 183 184 115 197 136 45 196 175 89 199 52 186 170 199 28 190 40 83 48 151 35 128 4 13 38 65 20 76 142 23 63 30 30 178 36 32 114 79 68 2 187 106 98 67 131 109 177 20 113 1 102 172 119 197 190 28 82 165 168 60 18 156 174 78 42 110 63 56 66 191 105 72 108 104 198 179 132 99 189 183 91 28 162 

출력

#1 2
#2 6
#3 108

My Sol

def QS(arr):
    def sort(s, e):
        if e <= s:
            return

        m = partition(s, e)
        sort(s, m-1)
        sort(m, e)
        return arr

    def partition(s, e):
        pivot = arr[(s+e)//2]
        while s <= e:
            while arr[s] < pivot:
                s += 1
            while arr[e] > pivot:
                e -= 1
            if s <= e:
                arr[s], arr[e] = arr[e], arr[s]
                s, e = s+1, e-1
        return s

    return sort(0, N-1)


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

특정 값을 pivot으로 설정하고, pivot의 앞쪽에는 pivot보다 값이 작은 배열을, pivot 뒤쪽에는 pivot보다 값이 큰 배열을 위치하여 분할하고, 이를 순서대로 배치하여 정렬하는 방식이다.

결과

PASS