[알고리즘] 퀵 정렬

퀵 정렬

정렬 알고리즘 중, 가장 많이 사용되는 알고리즘

기준을 설정한 다음, 큰 수와 작은 수를 교환한 후, 리스트를 반으로 나누는 방식
퀵 정렬에는 pivot이 사용됨(리스트의 첫번째를 피벗으로 정함)

• 피벗을 설정한 후,
• 왼쪽에서부터 피벗보다 큰 데이터를 찾고(while문의 조건 array[left] <= array[start]), 오른쪽에서부터 피벗보다 작은 데이터를 찾는다(while문의 조건 array[right] >= array[start]).
• 두 while문이 종료되었을 때,
• 작은 데이터의 위치와 큰 데이터의 위치를 확인한다.
  작은 데이터의 위치가 큰 데이터의 위치보다 크다면, 엇갈렸기 때문에 pivot과 작은 데이터를 교체한다.
  작은 데이터의 위치가 더 작다면, 작은 데이터와 큰 데이터를 교체한다.

널리 사용되고 있는 직관적인 소스코드

def quick_sort(array, start, end):
  # 배열 개수 1개인 경우 종료
  if start >= end:
    return
  pivot = start
  left = start + 1
  right = end
  while left <= right:
    # 피벗보다 큰 데이터 찾을 때까지 반복(작았을땐 반복)
    # left가 배열의 끝까지 가기 전까지
    while array[pivot] >= array[left] and left <= end:
      left += 1
    while array[pivot] <= array[right] and right > start: 
    # right >= start + 1 (처음 left의 위치)
      right -= 1
    if left < right: # 엇갈리지 않았을 때는 데이터 위치 바꿈
      array[right], array[left] = array[left], array[right]
    else: # 엇갈렸다면 pivot과 right(작은 데이터)를 바꿈
      array[pivot], array[right] = array[right], array[pivot]
  quick_sort(array, start, right - 1)
  quick_sort(array, right + 1, end)

파이썬 장점을 살린 소스코드

def quick_sort(array):
  if len(array) <= 1: # 배열 개수가 한개 이하일때 종료
    return array
  pivot = array[0]
  tail = array[1:] # 맨앞 원소 제외 리스트
  left_list = [x for x in tail if x <= pivot] # pivot 이하 값의 리스트
  right_list = [x for x in tail if x > pivot] # pivot보다 큰 값들의 리스트
  return quick_sort(left_list) + [pivot] + quick_sort(right_list)