[알고리즘] 퀵 정렬

퀵 정렬(Quick Sort)

퀵 정렬(Quicksort)은 찰스 앤터니 리처드 호어가 개발한 정렬 알고리즘이다.

다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.

퀵 정렬은 n개의 데이터를 정렬할 때, 최악의 경우에는 O(n2)번의 비교를 수행하고, 평균적으로 O(n log n)번의 비교를 수행한다.

개념

1. 두 개의 배열을 생성(front, back)
2. 중간 값(pivot) 보다 크면 뒤로 작으면 앞으로 이동
3. 더이상 중간 값이 없을 때 까지 1~2번 반복(재귀함수 사용)

코드

import collections

def quick_sort(arr):
    length = len(arr)

    if length <= 1:
      return arr

    mid = arr.pop(length//2)
    front = []
    back = []

    for i in arr:
      if i < mid:
        front.append(i)
      else:
        back.append(i)
     
  	return quick_sort(front) + [mid] + quick_sort(back)
    
print(quick_sort([4,3,2,1]))
# [1, 2, 3, 4]

Reference

제주 코딩 베이스 캠프 코딩 페스티벌 python 100제