[5.24] 06-6 퀵 정렬

퀵 정렬 quick sort

퀵 정렬 알아보기

피봇 pivot - 기준을 정하고 그룹을 나눈다. 그룹에 1명씩 남으면 정렬이 완료된다. 

배열을 두 그룹으로 나누기

- pl 왼쪽 커서, pr 오른쪽 커서로 설정해놓고, 피벗을 정한다. 

- pl을 오른쪽 방향으로 스캔하여 -> a[pl] > a[pivot]인 pl값을 찾는다.

- pr을 왼쪽 방향으로 스캔하여 -> a[pr] < a[pivot]인 pr값을 찾고, 두 값을 교환한다. 

- pl >= pr이 될 때까지 반복한다. 

 

두 그룹으로 나누는 걸 어떻게 구현해야 하나~

우선 while 구문에 들어가기 전에

n, pl, pr, pivot을 할당해주었다. 

while문 안에서

- pl >= pr이 되면 그만하고..

- a[pl] > a[pivot], a[pr] < a[pivot]이 되면 멈추고 교환해야 한다. 

 

from typing import MutableSequence

def quick(a:MutableSequence) -> None:
  n = len(a)
  pl = 0
  pr = n - 1
  x = a[n//2]

  while pl <= pr:
    while a[pl] < x: pl += 1
    while a[pr] > x: pr -= 1
    if pl <= pr:
      a[pl], a[pr] = a[pr], a[pl]
      pl += 1
      pr -= 1
  return a

print(quick([5, 4, 3, 2, 1]))

퀵 정렬 만들기

from typing import MutableSequence

def quick(a:MutableSequence, left:int, right:int) -> None:
  pl = left
  pr = right
  x = a[(left + right)//2]

  while pl <= pr:
    while a[pl] < x: pl += 1
    while a[pr] > x: pr -= 1
    if pl <= pr:
      a[pl], a[pr] = a[pr], a[pl]
      pl += 1
      pr -= 1

  if left < pr: quick(a, left, pr)
  if right > pl: quick(a, pl, right)

  return a

def quick_sort(a:MutableSequence) -> None:
  quick(a, 0, len(a)-1)
  return a

print(quick_sort([4, 5, 6, 1, 2, 3, 7]))

비재귀적인 퀵 정렬 만들기