[SWEA #11892] 분할정복 - 퀵정렬

문제

퀵 정렬을 구현해 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번 원소를 출력한다.

 

내가 쓴 코드 1 (틀림)

def quick_sort(s, e):
    pivot = arr[s]
    i, j = s, e
    while i <= j:
        while i <= j and arr[i] <= pivot:
            i += 1
        while i <= j and arr[j] >= pivot:
            j -= 1
        if i < j:
            arr[i], arr[j] = arr[j], arr[i]

    if s == j:
        return
    arr[s], arr[j] = arr[j], arr[s]
    if j > 0:
        quick_sort(s, j - 1)
    if j < e:
        quick_sort(j + 1, e)
    return arr

T = int(input())
for t in range(T):
    N = int(input())
    arr = list(map(int, input().split()))

    sorted_arr = quick_sort(0, N - 1)
    print(f'#{t+1} {sorted_arr[N//2]}')

강의자료에 있는 수도코드만 보고 작성한 코드.. 그래두 답은 나오는데 아쉽게 테케 한두개 정도 틀려서 아쉽,,

강사님이 강사님이 써주신 코드 거의 그대로 쓰면 맞는 문젠데 왜 못풀고 있냐고 그러심 ㅜㅜ 힝 몰랐어요... 언제 설명하셨어요 힝,,,

 

내가 쓴 코드 2 (맞)

def quick_sort(s, e):
    if s >= e: return
    pivot = arr[s]
    i, j = s, e
    while i <= j:
        while i <= j and arr[i] <= pivot:
            i += 1
        while i <= j and arr[j] >= pivot:
            j -= 1
        if i < j:
            arr[i], arr[j] = arr[j], arr[i]

    arr[s], arr[j] = arr[j], arr[s]
    quick_sort(s, j - 1)
    quick_sort(j + 1, e)

T = int(input())
for t in range(T):
    N = int(input())
    arr = list(map(int, input().split()))

    quick_sort(0, N - 1)
    print(f'#{t+1} {arr[N//2]}')

근데 퀵정렬 템플릿 코드 안보면 혼자선 못쓸듯.... ㅠㅠ

 

출력 결과

#1 2
#2 6
#3 108