quick sort

전체를 한꺼번에 정렬하려면 힘들다..

그럼 부분부분 나눠서 정렬하고 정렬된 부분들을 합치면 되지 않을까?

어떤 단위로 부분을 나눠야 할 까?

⇒ 가장 정렬하기 쉬운 단위

가장 정렬하기 쉬운 단위는 뭘까?

⇒ 요소가 1개 이하인 배열

⇒ 1개 이하면 정렬할 필요없이 리턴해버리면 됨

오름차순으로 정렬하려면 왼쪽 부분이 오른쪽 부분보다 작아야 함

왼쪽, 오른쪽 부분을 나누려면 기준이 있어야 함

기준이 될 임의의 숫자를 정하고 왼쪽은 기준 숫자보다 작은 요소로 이루어진 배열

오른쪽은 기준 숫자보다 큰 요소로 이루어진 배열로 나누자.

나누는 것을 가장 정렬하기 쉬운 단위 까지 나눠서 정렬된 부분을 재귀적으로 합치자

function quickSort(array) {
  if (array.length < 2) return array;

  const pivot = array[0];

  const less = array.filter((number) => number < pivot);
  const greater = array.filter((number) => number > pivot);

  return quickSort(less).concat([pivot]).concat(quickSort(greater));
}

console.log(quickSort([5,4,3,2,1]))

def quicksort(array):
    if len(array) < 2:
        return array

    pivot = array[0]

    less = list(filter(lambda x: x < pivot, array))
    greater = list(filter(lambda x: x > pivot, array))

    return quicksort(less)+[pivot]+quicksort(greater)

print(quicksort([5, 4, 3, 2, 1]))