고급 정렬(2) - 퀵 정렬(quick sort)

• 기준점(pivot)을 정해서 기준점보다 작은 데이터는 기준점 좌측에, 큰 데이터는 우측에 배치하는 함수를 작성
• 각 왼쪽, 오른쪽은 재귀용법을 사용하여 다시 동일 함수를 호출하여 위의 작업을 반복함
• 함수는 (왼쪽 + 기준점 + 오른쪽) 배열을 리턴함

 

function quickSort(data) {
  if (data.length <= 1) {
    return data;
  }
  const left = [];
  const right = [];
  const pivot = data[0];

  for (let i = 1; i < data.length; i++) {
    if (pivot > data[i]) {
      left.push(data[i]);
    } else {
      right.push(data[i]);
    }
  }

  return quickSort(left).concat([pivot].concat(quickSort(right)));
}