[Programming/Algorithm] 퀵 정렬(Quick Sort) with Python

알고리즘 중에 분할 정복 알고리즘(Divide and Conquer Algorithm)이 있다. 어려운 문제를 작게 쪼개서(divide) 해결해 나가는(conquer) 것을 말한다. 

대표적인 분할 정복 알고리즘인 퀵 정렬에 대해 알아보자.

퀵 정렬

pivot은 정렬되지 않은 리스트에서 가운데 위치한 인덱스의 데이터를 말한다. 주의할 점은 인덱스가 아니라 데이터라는 것이다. start는 첫 번째 인덱스이고 end는 미자막 인덱스이다. left와 right는 각각 start와 end를 가리킨다.

left 인덱스는 오른쪽으로 이동하고 right 인덱스는 왼쪽으로 이동한다. 목적은 pivot을 기준으로 왼쪽은 pivot보다 작은 데이터가 모이고, 오른쪽은 큰 데이터가 모이도록 만드는 것이다.

그렇게 하려면 left는 오른쪽으로 이동하다가 pivot보다 큰 데이터를 만나면 멈춰야한다. right는 왼쪽으로 이동하다가 pivot 보다 작은 데이터를 만나면 멈춰야한다. 그리고 두 데이터를 교환한다.

import random


def quick_sort(data, start, end):
    if start >= end:
        return
    left = start
    right = end
    pivot = data[(start + end) // 2]

    # left와 right가 교차할 때까지 반복
    while left <= right:
        # left 데이터가 pivot보다 크거나 같으면 멈춘다.
        while data[left] < pivot:
            left += 1
        # right데이터가 pivot보다 작거나 같으면 멈춘다.
        while data[right] > pivot:
            right -= 1

        # left와 right가 교차하지 않았다면 교환
        if left <= right:
            data[left], data[right] = data[right], data[left]
            left += 1
            right -= 1

    quick_sort(data, start, right)
    quick_sort(data, left, end)


if __name__ == '__main__':
    random.seed(0)
    data_lst = [int(random.random() * 50) for i in range(15)]
    print(data_lst)
    quick_sort(data_lst, 0, len(data_lst) - 1)
    print(data_lst)


""" 결과

[42, 37, 21, 12, 25, 20, 39, 15, 23, 29, 45, 25, 14, 37, 30]
[12, 14, 15, 20, 21, 23, 25, 25, 29, 30, 37, 37, 39, 42, 45]

"""

이제 start부터 right까지 이 과정을 반복하고 left부터 end까지도 이 과정을 반복한다. 같은 알고리즘의 반복을 구현할 때는 재귀 함수를 이용한다. 탈출 조건은 start가 end보다 크거나 같아지는 지점이다. 바로 정렬하려는 데이터가 하나일 때까지 쪼개어(divide) 문제를 해결하는(conqure) 분할 정복 기법이다.

C언어의 Quick Sort

2021.03.11 - [Programming/Algorithm] - [Programming/Algorithm] 퀵 정렬(Quick Sort)

[Programming/Algorithm] 퀵 정렬(Quick Sort)