QuickSort.js

QuickSort.js

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

  const pivot = array[0];

  let leftCursor = 1;
  let rightCursor = array.length - 1;
  
  // left Cursor가 rightCursor와 만나는 순간 까지
  while(leftCursor <= rightCursor) {

    /*
      swap
      각 조건, 
      1. pivot보다 좌측부터 시작한값이 크거나 우측에서 시작한값이 pivot보다 작다면 swap하고, 인덱스값을 1씩 올린다.
      2. array[leftCursor] 값이 pivot보다 작거나 같다면 leftCursor를 1 올린다. (왼쪽부터 증가하는 값)
      3. array[rightCursor] 값이 pivot보다 크거나 같다면 rightCursor를 1내린다. (오른쪽부터 감소하는 값)
    */
    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)
  ];
}


// stable version
function quickSort (array) {
  
  if (array.length < 2) {
    return array;
  }
  
  const pivot = [array[0]];
  const left = [];
  const right = [];
  
  for (let i = 1; i < array.length; i++) {  
    if (array[i] < pivot) {
      left.push(array[i]);
    } else if (array[i] > pivot) {
      right.push(array[i]);
    } else {
      pivot.push(array[i]);
    }
  }
  
  console.log(`left: ${left}, pivot: ${pivot}, right: ${right}`);
  return quickSort(left).concat(pivot, quickSort(right));
}

const sorted = quickSort([5, 3, 7, 1, 9]);
console.log(sorted);