이코테-chapter6: 퀵 정렬

정리 내용

퀵 정렬

• 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작.
• 큰 숫자와 작은 수를 교환할 때, 피벗(pivot)을 사용한다.
• 퀵 정렬을 수행하기 전에는 피벗을 어떻게 설정할 것인지를 생각해야 한다.
• 대개 분할(divide) 혹은 파티션(partition)으로 설정한다.
• 시간 복잡도 평균: O(N*logN), 최악의 경우: O(N^2)
• 정렬할 데이터의 개수가 많을수록 더 효율적이다.

퀵 정렬 소스코드

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

def quick_sort(array):
    # 리스트가 하나 이하의 원소만을 담고 있다면 종료
    if len(array) <= 1:
        return array
    
    pivot = array[0]  # 피봇은 첫 번째 원소
    tail = array[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))

출처 && 깃허브

이것이 취업을 위한 코딩 테스트다 with python

github