퀵 정렬(2) 호어 분할 방식 구현 / Python

호어 분할 방식 구현하기 / Python

- 퀵 정렬에 대해 알아보고, 첫 번째 데이터를 피벗(Pivot)으로 사용하는 호어 분할 방식의 전체적인 과정은 위와 같다

- 예제로 들었던 배열을 사용해, 퀵 정렬을 파이썬으로 구현해 보도록 하자

 

 

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

- 예제의 데이터를 배열의 형태로 선언하여 사용한다

 

 

def quick_sort(arr, start, end):
    if start >= end: # 요소가 하나인 경우 종료
        return

    pivot = start        # 호어 방식이므로 첫번째 데이터를 pivot으로 사용한다
    left = start + 1     # 왼쪽 데이터는 pivot의 바로 오른쪽 데이터를 사용한다
    right = end          # 오른쪽 데이터로 마지막 데이터를 사용한다

    while left <= right:
    	# 왼쪽 데이터 중, 피벗보다 큰 데이터를 찾는다
        while left <= end and arr[left] <= arr[pivot]:
            left += 1
            
        # 오른쪽 데이터 중, 피벗보다 작은 데이터를 찾는다
        while right > start and arr[right] >= arr[pivot]:
            right -= 1
            
        # 큰 데이터와 작은 데이터가 서로 엇갈린 경우, 작은 데이터와 피벗의 위치를 서로 변경한다
        if left > right:
            arr[right], arr[pivot] = arr[pivot], arr[right]
        # 엇갈리지 않는 경우 작은 데이터와 큰 데이터의 위치를 바꾼다
        else:
            arr[left], arr[right] = arr[right], arr[left]

	# 분할 이후, 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행한다
    quick_sort(arr, start, right-1)
    quick_sort(arr, right+1, end)

- 가장 직관적인 형태의 전통 퀵 정렬 소스 코드이다

 

 

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)

- 파이썬의 장점을 극대화한 퀵 정렬 소스 코드이다 

- 배열의 첫번째 index를 의미하는 start, 마지막 index를 end를 파라미터로 받지 않고 내부 로직에서 처리한다

- 전통 퀵 정렬 분할방식과 달리 피벗과 데이터를 비교하는 비교 연산 횟수는 증가해 시간면에서는 비교적 비효율적이다

- 하지만 더 직관적이고 기억하기 쉬운 코드의 형태이다