TIL 8 - 정렬 (sorting) : 퀵 정렬

지난 정렬 포스팅에 이어서

퀵 정렬 (quick sort)

• 이름 처럼 '퀵'한 정렬. 정렬 알고리즘의 꽃이라 할 수 있다.
• pivot (기준점) 을 정해서 pivot 보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 정렬한다.

알고리즘

• 리스트의 첫번째 데이터를 pivot 으로 정한다.
• pivot 과 현재 데이터를 비교하여 pivot 보다 작으면 왼쪽 list에 크면 오른쪽 list에 저장한다.
• 리스트의 데이터 길이가 1이 될 때까지 재귀적으로 위의 과정을 반복하고 왼쪽 list + pivot + 오른쪽 list 값을 호출한다.

파이썬으로 구현해 보기

def qsort(data):
  if len(data) <= 1:
    return data
  
  left, right = [], []
  pivot = data[0]

  for i in range(1,len(data)):
    # pivot 보다 작으면 왼쪽 리스트에 추가
    if pivot > data[i]:
      left.append(data[i])
    # pivot 보다 크면 오른쪽 리스트에 추가
    else:
      right.append(data[i])
  # 리스트끼리는 + 하기위해 [pivot] 으로 형변환
  return qsort(left) + [pivot] + qsort(right)

퀵 정렬의 시간복잡도는 O(n logn) 이다.
logn 만큼의 단계가 생성이 되고 각 단계별로 n 만큼의 시간이 걸린다.

(단, 최악의 경우 O(n^2) 까지 나올 수 있다)