퀵소트 파이썬 코드 (quick_sort)

동빈나 유튜브 내용

• 링크 : https://youtu.be/EuJSDghD4z8

---

코드

• 베이직 버전

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

def quick_sort(arr, start, end):
    if start >= end:   #원소가 1개인 경우 종료
        return
    
    # 시작점, 끝점과 별개로 이동할 때 필요하므로 사용
    pivot = start
    left = start + 1
    right = end
    
    # 엇갈릴 때까지 반복
    while left <= right:
        # (->) 왼쪽이 마지막 인덱스 전까지 & 피벗보다 큰 데이터를 찾을 때까지 반복
        while left<=end and arr[left] <= arr[pivot]:     # = 작으면 패스
            left += 1
            
        # (<-) 오른쪽이 맨앞 인덱스 전까지 & 피벗보다 작은 데이터를 찾을 때까지 반복
        while start < right and arr[pivot] <= arr[right]:  # = 크면 패스
            right -= 1
            
        # 엇갈렸어 ~> 피벗과 작은값 swap
        if right < left:    
            arr[pivot], arr[right] = arr[right], arr[pivot]  # 값을 바꾸는거 (idx 그대로!)
        # 아니야 ~> 둘이 swap
        else:
            arr[left], arr[right] = arr[right], arr[left]            
            
    # Swap된 Right를 기준으로 Recursive하게 수행
    quick_sort(arr, start, right-1)  # 왼쪽 수행
    quick_sort(arr, right+1, end)    # 오른쪽 수행


quick_sort(arr, 0, len(arr)-1)  # 정렬할것, 시작, 끝
print(arr)

• 파이썬 버전

''' 간단 버전 - 파이썬 '''

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

def quick_sort(arr):
    #원소가 1개인 경우 종료
    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]  # 피벗보다 큰 것만 오른쪽에 모아(정렬되진 않음)
    
    # 피벗의 위치만 확정이고, 작은 < 피벗 < 큰  순서의 배열로 Recursive
    return quick_sort(left_side) + [pivot] + quick_sort(right_side)
    
print(quick_sort(arr))