뼈속 깊이 이해하기 :: 3. 퀵소트

뼈속 깊이 이해하기 :: 3. 퀵 소트

Quick Sort - 피봇을 왼쪽 가장자리로 잡을 때.

핵심 원리

• lp는 정렬할 배열의 왼쪽 끝에서 시작, rp는 오른쪽 끝에서 시작.
  • lp는 피봇값보다 작거나 같은 값들일 경우에 계속해서 지나친다.
  • lp가 지난 슬롯들은 모두 피봇보다 작거나 같다는 것이 증명이 된다.
• rp는 피봇값보다 크거나 같은 값들일 경우에 계속해서 지나친다.
  • rp가 지난 슬롯들은 모두 피봇보다 크거나 같다는 것이 증명이 된다.
• lp < rp를 만족한다면 두 값을 스왑한 후 위의 1- 2 과정을 반복한다.
• lp는 피봇이 위치할 장소를 찾는다. 즉 lp - 1을 pivot과 바꾸기만해도 왼쪽 끝부터 lp - 1까지 정렬된 것을 확신할 수 있다.
  • 또한 rp의 오른쪽은 피봇보다 크거나 같다는 것을 확신할 수 있다.
  • 따라서 바꾼후 피봇의 오른쪽까지 정렬되게 하려면, pivot과 rp가 일치해야한다.
  • 결론, lp - 1위치에 rp가 왔을 때 rp와 바꾸면 정렬이 완료된다.

import sys
sys.setrecursionlimit(10 ** 8)
read = sys.stdin.readline
n = int(read())
inputs = [0] * n
for i in range(n):
    inputs[i] = int(read())

def swap(inputs, x, y):
    tmp = inputs[x]
    inputs[x] = inputs[y]
    inputs[y] = tmp 
    return 

def quick_sort(inputs, l, r):
    if r - l <= 1:
        return 
    pivot = l 
    lp = l
    rp = r - 1
    while(lp <= rp):
        while(lp < r and inputs[lp] <= inputs[pivot]):
            lp += 1
        while(lp <= rp and inputs[rp] >= inputs[pivot]):
            rp -= 1
        if lp < rp:
            swap(inputs, lp, rp)
    swap(inputs, pivot, rp)
    pivot = rp 
    
    quick_sort(inputs, l, pivot)
    quick_sort(inputs, pivot + 1, r)
    return 
                
quick_sort(inputs, 0, len(inputs))
for x in inputs:
    print(x)