[Algorithm] 퀵 정렬(Quick Sort)

퀵 정렬(quick sort) ?

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

def qsort(data):
  if len(data) <= 1:
    return data
  
  pivot = data[0] #리스트 맨 앞의 데이터를 기준점(pivot)으로 놓기
  
  #1.default
  left, right = list(), list()
  for index in range(1, len(data)):
    if pivot > data[index]:
      left.append(data[index])
    else:
      right.append(data[index])
      
  #2.list comprehension 사용
  left = [item for item in data[1:] if pivot > item]
  right = [item for item in data[1:] if pivot <= item]
      
  return qsort(left) + [pivot] + qsort(right) #리스트를 덧셈연산을 통해 합칠 수 있다