퀵 정렬

퀵 정렬은 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다.

array = [5,7,9,0,3,1,6,2,4,8]

def quick_sort(array):
  # 리스트가 하나 이하의 원소만을 담고 있다면 종료
  if len(array) <= 1:
    return array
  pivot = array[0] # 피벗은 첫 번째 원소
  tail = array[1:] # 피벗을 제외한 리스트

  # 분할 된 왼쪽 부분(pivot보다 작거나 같은 수)
  left_side = [x for x in tail if x <= pivot] 
  # 분할 된 오른쪽 부분 (pivot보다 큰 수)
  right_side = [x for x in tail if x > pivot]
  # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환
  return quick_sort(left_side) + [pivot] + quick_sort(right_side)

print(quick_sort(array))

파이썬에 최적화 된 퀵정렬 방식이다.

피벗(가장 첫 번째 원소)를 정하고 피벗을 기준으로 작은수는 왼쪽(left_side) 큰 수는 오른쪽 (right_side)로 지정해줘서 재귀함수로 부분을 나누어서 return해준다.

퀵정렬의 시간 복잡도는 NlogN이다 다른 정렬보다 빠른 시간 복잡도를 가진다