퀵소트

분할정복 개념 :"어려운 문제를" 잘게 "쪼개서" divide 작게 쪼개진 문제 "문제" 하나씩

"해결"함으로써 "작은 solution"이 모여서 전체 문제에 대한 "solution"을 구하는기법

 

def quick_sort(li, start, end):
    #base case
    #to do
    if start >= end:
        return
    
    left=start
    right=end
    pivot=li[(left+right)//2]
    
    while left <= right:
        while li[left] < pivot:
            left+=1
            
        while pivot < li[right]:
            right-=1
            
        if left <= right:
            li[left], li[right] = li[right],li[left]
            left+=1
            right-=1
    quick_sort(li, start, right)
    quick_sort(li, left, end)
            

import random
if __name__=="__main__":
    while True:
        num_data=int(input('데이터 개수(종료:0):'))
        if not num_data:
            break
        data=[random.randint(1, 100) for _ in range(num_data)]
        print(data)
        quick_sort(data, 0, len(data)-1)
        print(data)