자바스크립트 알고리즘 - 퀵정렬 (quick sort)

설명

• https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
• https://www.zerocho.com/category/Algorithm/post/57f72d415141fc5fe4f4ca8b

  원리를 설명하기에는 벅차서 위의 링크를 참조해 주시면 좋겠네요. 소스코드 위주로 작성해보겠습니다. 이해하기가 생각보다 어려울 수 있지만 차근차근 보고 또 보다보면 어느새 소스코드로 옮길 수 있게 됩니다.

소스코드

/**
 * @see https://gmlwjd9405.github.io/2018/05/10/algorithm-quick-sort.html
 */
function quickSort(array) {
  if (array.length < 2) return array;

  const pivot = array[0];

  let leftCursor = 1;
  let rightCursor = array.length - 1;
  while(leftCursor <= rightCursor) {
    
    // 왼쪽수가 기준보다 크고 오른쪽 수가 기준보다 작으면 위치를 바꿉니다 (swap)
    if (array[leftCursor] > pivot && array[rightCursor] < pivot) {
      [array[leftCursor], array[rightCursor]] = [array[rightCursor], array[leftCursor]];
      leftCursor++;
      rightCursor--;
    }

    // 왼쪽 수는 기준보다 작으면 다음으로 넘어가고, 크면 가만히 있습니다
    if (array[leftCursor] <= pivot) {
      leftCursor++;
    }

    // 오른쪽 수는 기준보다 크면 다음으로 넘어가고, 작으면 가만히
    if (array[rightCursor] >= pivot) {
      rightCursor--;
    }
  }

  [array[0], array[leftCursor-1]] = [array[leftCursor-1], array[0]];
  const left = array.splice(0, leftCursor-1);
  const mid = array.splice(0, 1);
  const right = array;

  return [
    ...quickSort(left),
    ...mid,
    ...quickSort(right)
  ];
}


const result = quickSort([5,3,8,4,9,1,6,2,7]);

Github

• https://github.com/leejinseok/javascript-algorithm/blob/master/quick-sort.js