[SWEA] 16940. 퀵 정렬

퀵 정렬

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

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**으로 설정합니다.
```python
        # 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]}')

5. 후기

• 저한텐 굉장히 어려웠습니다... 가장 빠른 정렬... 가장 중요한 정렬이라 하지만 익숙하게 쓸 수 있어야 효율적이고 유익한 코드겠죠. 같이 열심히 배우고 익혀봅시다.

6. 번외 - pivot 값이 가장 첫 번째 값일 때

 

노란색이 pivot, 초록색이 pivot보다 작은 데이터, 보라색이 pivot보다 큰 데이터, 주황색이 정렬이 끝난 데이터입니다.