[SWEA] 5205 퀵정렬

문제 링크: SWEA 5205. [파이썬 S/W 문제해결 구현] 4일차 - 퀵 정렬

풀이

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)  # 피봇 기준 오른쪽 정렬

def partition(a, l, r):
    p = a[l]  # p: 피봇 값
    i = l + 1  # 첫 번째 값은 피봇으로 사용함
    j = r

    while i <= j:
        while i <= j and a[i] <= p:  # i는 피봇보다 큰 값을 가리킴
            i += 1
        while i <= j and a[j] >= p:  # j는 피봇보다 작은 값을 가리킴
            j -= 1

        if i <= j:
            a[i], a[j] = a[j], a[i]  # 작은값은 왼쪽, 큰값은 오른쪽

    a[l], a[j] = a[j], a[l]  # 피봇을 작은값과 큰값의 센터에 둠

    return j


for test_case in range(1, int(input()) + 1):
    n = int(input())
    array = list(map(int, input().split()))

    quick_sort(array, 0, len(array) - 1)
    print(f'#{test_case} {array[n//2]}')

설명

• 맨 왼쪽에 있는 값을 피봇값으로 하고 피봇값보다 작은 값들을 왼편, 큰 값들을 오른편에 위치시킨다. 그리고나서 피봇값을 큰값과 작은값의 사이인 가운데에 놓는다. 다시 피봇값을 기준으로 왼쪽과 오른쪽 구역을 나누고 배열을 각각 정렬하는것을 반복한다.

• 반복문에서 i를 계속 증가시켜 i는 피봇보다 큰 값을 가리키게 되고 j는 계속 감소시켜서 피봇보다 작은 값을 가리키게 된다.

• i와 j가 교차하여 지나는 지점은 왼쪽방향에 j가 가리키는 작은값, 오른쪽 방향에 i가 가리키는 큰값이 있다는 의미이고 그 사이에 피봇값을 위치시킨다. ➡ j(피봇보다 작은 값이 위치한 곳)와 l(피봇이 위치한 곳)에 위치한 원소를 swap한다.