퀵정렬(quick sort) - 전위순회방식의 DFS

0. 병합정렬 vs 퀵정렬

퀵 정렬(quick sort)을 공부했다! 이건 병합정렬처럼 재귀적 구조를 가지기는 하지만, 확연히 다른 점이 있다.

바로 "전위순회방식"을 취한다는 점.

즉 자기 레벨에서 지정된 피봇으로 해야 할 작업을 모두 다 진행한 후에!

그래서 피봇이 자기 자리를 땅땅!! 확신한 후에!

이제 피봇위치 기준 좌우로 잘라서 자식들을 만들고,

그 자식들/아래 레벨들에 대해서도 다시 피봇을 설정해 같은 작업을 반복하도록 재귀적으로 호출해주는 것이다.

병합정렬의 경우에는 자식이 처리를 다했어야 자신이 할 일을 할 수 있었던 "후위순회방식"과 대조를 이룬다.

 

1. 손으로 하는 공부

 시간을 꽤 들이기는 했어도, 나의 머리에 좀 더 우직히 퀵 정렬이 자리잡기를 바라는 마음으로 🤓📝

2. 코드

arr = [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]

def Qsort(lt, rt):
    if lt < rt:
        pos = lt
        pivot = arr[rt]
        for i in range(lt, rt):
            # 엇 나보다 작은 값 발견했다면 앞쪽으로 보내줘야지
            # 저 앞에 pos 값하고 스왑해주자
            # 이제 pos 자리는 나(pivot)보다 작은 애로 잘 채웠으니까,
            # 다음에 작은애가 오면 그 다음칸에 채워줘야하니
            # pos 는 한 칸 앞으로 이동하자!
            if arr[i] <= pivot:
                arr[i], arr[pos] = arr[pos], arr[i]
                pos += 1
        arr[rt], arr[pos] = arr[pos], arr[rt]
        Qsort(lt, pos-1)
        Qsort(pos+1, rt)

Qsort(0, 9)
print(arr)