[파이썬][알고리즘] 퀵 정렬 (분할 정복)

퀵 정렬 (quick sort)

퀵 정렬

• 정렬 알고리즘의 핵심.
• 기준점 (pivot)을 정해서 pivot보다 작은 데이터는 왼쪽으로, 큰 데이터는 오른쪽으로 모으는 함수를 작성한다.
• 각 왼쪽, 오른쪽으로 모인 수는 재귀 함수를 이용하여 위 과정을 반복한다.

pivot 설정

나누기

왼쪽 오른쪽에서 각각 반복

합치기

알고리즘 작성

def qsort(list_num):
    if len(list_num) <= 1:
        return list_num

    left, right = list(), list()
    pivot = list_num[0]

    for i in range(1, len(list_num)):
        if pivot > list_num[i]:
            left.append(list_num[i])
        else:
            right.append(list_num[i])

    return qsort(left) + [pivot] + qsort(right)

import random

list_num = random.sample(range(100), 10)
qsort(list_num)

[1, 3, 9, 15, 17, 38, 41, 62, 90, 96]

def qsort(list_num):
    if len(list_num) <= 1:
        return list_num

    pivot = list_num[0]

    left = [num for num in list_num[1:] if pivot > num]
    right = [num for num in list_num[1:] if pivot < num]

    return qsort(left) + [pivot] + qsort(right)

import random

list_num = random.sample(range(100), 10)
qsort(list_num)

[13, 26, 43, 50, 53, 68, 73, 75, 87, 91]

• 시간 복잡도: O($nlogn$)
  • 최악의 경우 O($n^2$)
    • 제일 처음 pivot이 가장 크거나 가장 작은 경우