[Python Algorithm] 퀵 정렬

 

import sys
input = sys.stdin.readline

def Qsort(lt, rt):
  if lt<rt:
    pos = lt
    pivot = arr[rt]
    for i in range(lt, rt):
      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)


arr = [45, 21, 23, 36, 15, 67, 11, 60, 20, 33]
print("Before sort : ", end='')
print(arr)
Qsort(0,9)
print()
print("After sort : ", end='')
print(arr)

 

 

⭐️ Point ! ⭐️

 

• arr[i] 값과 pivot을 비교하여 pivot값보다 작으면 arr[pos]와 arr[i] 값을 바꾼다. swap 했으면 pos +1
• for문이 한번 끝났으면 arr[pos]와 pivot값을 바꾼다.
• 그러면 결국 정해진 피봇보다 작은 값은 피봇의 왼쪽, 큰 값은 피봇의 오른쪽으로 가게 됨.
  
•  

 

• 이제 왼쪽 오른쪽 값이 한번 정렬되었으므로
  
  
• 가장 중간값 pos 값을 기준으로 Q(lt, pos-1), Q(pos+1, rt)를 수행

 

출처

• 인프런 : 파이썬 알고리즘 문제 풀이