퀵 소트

array=[5,7,9,0,3,1,6,2,4,8]

def quick_sort(array,start,end):
    if start>=end:
        return
    pivot=start
    left=start+1
    right=end

    while left<=right:
        while left<=end and array[left]<=array[pivot]:
            left+=1
        while right>start and array[right]>=array[pivot]:
            right-=1

        if left>right: # 엇갈렸다면 작은 데이터와 피벗 교체
            array[right],array[pivot]=array[pivot],array[right]
        else: #엇갈리지 않았다면 작은데이터와 큰 데이터 교체
            array[left],array[right]=array[right],array[left]

    quick_sort(array,start,right-1)
    quick_sort(array,right+1,end)

quick_sort(array,0,len(array)-1)
print(array)

파이썬을 활용한 퀵 소트 (easy)

array=[5,7,9,0,3,1,6,2,4,8]

def quick_sort(arr):
    if len(arr)<=1:
        return arr

    pivot=arr[0] #피벗은 첫번째 원소
    tail=arr[1:] # 피벗 제외한 리스트

    left_side=[x for x in tail if x<=pivot] # 분할된 왼쪽 부분
    right_side=[x for x in tail if x>pivot] # 분할된 오른쪽 부분

    return quick_sort(left_side)+[pivot]+quick_sort(right_side)


print(quick_sort(array))
    

• devide and conquer 방식
• 피봇을 정하고, 피봇보다 왼쪽에는 피봇보다 작은 수/ 오른쪽에는 피봇보다 큰 수로 분할 후 다시 합침.
• 재귀 함수를 사용. 정렬하는 array의 길이가 1이 되면 탈출.
• 시간복잡도 O(nlogn)/ 최악의 경우는 O(n^2)