퀵 정렬(quick sort)

분할 정복 알고리즘의 대표적인 예

1. 보통 리스트의 첫 번째 원소를 기준점(pivot)으로 한다
2. pivot보다 작은 데이터는 left 리스트, 큰 데이터는 right 리스트에 더한다
3. left 리스트 + [pivot] + right 리스트를 리턴한다
  3-1. left, right 리스트는 재귀용법을 사용해서 위 작업을 반복한다
4. 리스트의 길이가 1이면 해당 리스트를 반환한다
* 시간복잡도 O(n logn) / 최악의 경우 O(n^2)

import random

def quick_sort(data):
    if len(data) <=1:
        return data

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

    for x in range(1, len(data)):
        if data[x] < pivot:
            left.append(data[x])
        else:
            right.append(data[x])
    return quick_sort(left) + [pivot] + quick_sort(right)

data = random.sample(range(10), 5)

print(data) # [2, 9, 5, 7, 4]
print(quick_sort(data)) # [2, 4, 5, 7, 9]

- 리스트 컴프리헨션을 사용했을 때 코드는 훨씬 간결해진다!

import random

def quick_sort(data):
    if len(data) <=1:
        return data

    pivot = data[0]

    left = [ n for n in data[1:] if n < pivot ]
    right = [ n for n in data[1:] if n >= pivot ]

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

data = random.sample(range(10), 5)

print(data) # [8, 4, 2, 0, 6]
print(quick_sort(data)) # [0, 2, 4, 6, 8]

  - 출처 : fastcampus