퀵 정렬(Quick Sort)

• 정렬 알고리즘의 꽃이다.
• 기준점(pivot)을 정해서, 기준점보다 작은 데이터는 왼쪽 리스트, 큰 데이터는 오른쪽 리스트로 모으는 정렬방법이다.
• 왼쪽, 오른쪽은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복한다.
• 함수는 왼쪽 리스트 + 기준점(pivot) + 오른쪽 리스트을 리턴한다.

시간 복잡도

• 병합정렬과 유사하다.
• $O(nlogn)$이다.
  • 단, 최악의 경우에 맨 처음 pivot이 가장 크거나, 가장 작으면 모든 데이터를 비교하는 상황이 나온다.
    

퀵 정렬 구현

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

Python Comprehension

def quickSort(data_list):
    if len(data_list) <= 1:
        return data_list
    
    pivot = data_list[0]
    left = [i for i in data_list[1:] if pivot > i]
    right = [j for j in data_list[1:] if pivot <= j]
    
    return quickSort(left) + [pivot] + quickSort(right)