quickSort 구현

랜덤 피봇 방법(random pivot)

import random

def swap(array, i, j): #array[i] 값과 array[j] 값 swap 함수
    tmp = array[i]
    array[i] = array[j]
    array[j] = tmp

def quick_sort(array, start, end):  #랜덤피봇의 퀵정렬
    if start >= end: #원소가 1개인 경우
        return 
    else:
        p = partition(array, start, end) #기준 피봇 결정
        quick_sort(array, start, p-1) #피봇기준 왼쪽 부분 재귀호출
        quick_sort(array, p+1, end) #피봇기준 오른쪽 부분 재귀호출

        return array

def partition(array, start, end):
        pivot_index = random.randint(start, end+1) #randint(n,m) n ~ m-1 까지 범위에서 난수 생성
        pivot = array[pivot_index]

        swap(array, pivot_index, end) #end(맨오른쪽)과 피봇과 값을 swap

        temp_index = start

        for i in range(start,end):
            if array[i] < pivot:
                swap(array, i, temp_index)
                temp_index += 1
        swap(array, end, temp_index)

        return temp_index

실행

data = [10, 3, 6, 2, 5, 1, 9, 8]
print(quick_sort(data, 0, len(data)-1))

실행결과

[1, 2, 5, 6, 8, 3, 9, 10]

피봇을 첫번째 원소로 설정하는 방법

def quick_sort(array, start, end):
    if start >= end: # 원소가 1개인 경우 종료
        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)

실행

data = [10, 3, 6, 2, 5, 1, 9, 8]
print(quick_sort(data, 0, len(data)-1))

실행결과

[1, 2, 5, 6, 8, 3, 9, 10]