[알고리즘] 퀵 정렬 Quick Sort

퀵 정렬이란

• 굉장히 효과적인 정렬 알고리즘
• Pivot을 정한 뒤, 다른 데이터를 pivot과 비교해서 작으면 왼쪽, 크면 오른쪽으로 정렬
• 이 과정을 재귀적으로 반복한다
• 시간 복잡도 : O(n logn)

 

알고리즘 구현하기

def qsort(data):
    if len(data) <= 1:
        return data
    
    left, right = list(), list()
    pivot = data[0]
    
    for index in range(1, len(data)):
        if pivot > data[index]:
            left.append(data[index])
        else:
            right.append(data[index])
    
    return qsort(left) + [pivot] + qsort(right)

import random

data_list = random.sample(range(100), 10)

qsort(data_list)

Out[6]: [3, 11, 21, 26, 41, 57, 64, 66, 75, 96]

 

파이썬 comprehensive를 이용해서 구현하기

def qsort(data):
    if len(data) <= 1:
        return data
    
    pivot = data[0]
    
    left = [item for item in data[1:] if pivot > item]
    right = [item for item in data[1:] if pivot <= item]
    
    return qsort(left) + [pivot] + qsort(right)

import random

data_list = random.sample(range(100), 10)

qsort(data_list)

Out[13]:

[5, 19, 30, 31, 53, 55, 77, 87, 95, 98]

 

GitHub - DAWUNHAN/Algorithms-and-DataStructure: Algorithms and DataStructure with Python