[SWEA] 16940. 퀵 정렬

성제현·2023년 3월 29일

SSAFY SWEA python 정렬 퀵 정렬

Algorithm[python]

목록 보기

3/6

퀵 정렬

퀵 정렬... 말 그대로 가장 빠른 정렬 알고리즘 입니다. 바로 알아봅시다.

1. 퀵 정렬 동작 과정

퀵 정렬 함수 코드

def quick_sort(lst):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        # 중간값 pivot을 찾습니다.
        pivot = lst[(low + high) // 2]
        while low <= high:
            while lst[low] < pivot:
                low += 1
            while lst[high] > pivot:
                high -= 1
            if low <= high:
                lst[low], lst[high] = lst[high], lst[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, len(lst) - 1)

우선 퀵 정렬의 첫 번째는 pivot 설정 입니다.
이해를 위해 예시 하나를 넣어서 설명하겠습니다.

lst = [2, 2, 1, 1, 3]

위 함수로 들어가게 된다면 quick_sort() 함수의 return에 따라 sort() 함수가 작동하게 됩니다. 그때 low 와 high 값은 0과 len(lst)-1 즉, 4가 되겠네요.

    def sort(low, high):
        if high <= low:
            return
        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

if 조건문은 넘어가게 됩니다. 따라서 mid의 값을 설정하기 위해 partition() 함수를 수행합니다.

일반적으로 list의 중간값을 pivot으로 설정합니다.
		# low = 0, high = len(lst)-1
        pivot = lst[(low + high) // 2]
low = 0, high = 4, pivot은 lst[2], 즉 pivot = 1 입니다.

pivot을 설정했으면 pivot을 기준으로 왼쪽은 pivot 보다 작은 데이터, 오른쪽은 pivot 보다 큰 데이터로 구분합니다.

        while low <= high:
            while lst[low] < pivot:
                low += 1
            while lst[high] > pivot:
                high -= 1
            if low <= high:
                lst[low], lst[high] = lst[high], lst[low]
                low, high = low + 1, high - 1
            return low

while 문을 이용해 low의 값이 high 보다 크거나 같을 때 까지 반복합니다.
만약 lst[low] 의 값이 pivot 보다 작다면! low += 1 해줍니다.
그림에서는 lst[low] 가 pivot 보다 크죠? 그럼 넘어가고 lst[high] 는 pivot 보다 큽니다.
그럼 high -=1 해줍시다.

바뀐 인덱스로 배정된 그림을 살펴 봅시다.

이번엔 lst[high] 가 pivot 과 같기 때문에 while 문을 무사히 통과 합니다.
if 문으로 들어가보죠! low <= high 조건이 맞습니다. 그럼 low와 high 위치의 원소를 서로 바꿔줍시다.

다음으로 low 와 high 에 각각 +1 -1 을 해줍니다.

다시 처음 while 문으로 돌아와서 조건을 통과하게 되고 2번째 while 문, 3번째 while문도 통과하게 됩니다. 다시 if 문으로 돌아와 low <= high 의 조건에 부합하여 해당 위치의 원소들을 바꿔줍니다. 그리고 low 와 high 에 각각 +1 -1 해줍시다.

그럼 다음 그림과 같이 변하게 되고 while문을 탈출하게 되고 low 값을 return 합니다.
( low = 2 )

    def sort(low, high):
        if high <= low:
            return
        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)
다시 mid의 값이 2 로 설정되었으니 다음 동작을 수행합니다. sort(2, 1) 이 되겠네요.
그럼 low = 2, high = 1 이므로 low값이 더 크게 됩니다. 그러므로 return 하여 sort() 함수를 종료하고 전체 함수가 끝나게 됩니다.

3. 문제 설명

단순하게 입력에 주어지는 숫자 리스트를 정렬하고 N//2 번째 인덱스의 원소를 출력하면 됩니다.

4. 전체 코드

def quick_sort(lst):
    def sort(low, high):
        if high <= low:
            return

        mid = partition(low, high)
        sort(low, mid - 1)
        sort(mid, high)

    def partition(low, high):
        # 중간값 pivot을 찾습니다.
        pivot = lst[(low + high) // 2]
        while low <= high:
            while lst[low] < pivot:
                low += 1
            while lst[high] > pivot:
                high -= 1
            if low <= high:
                lst[low], lst[high] = lst[high], lst[low]
                low, high = low + 1, high - 1
        return low

    return sort(0, N - 1)

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