자바스크립트로 퀵 정렬 구현하기

1. pivot값이 처음 값인 경우

let arr = [1,4,5,2,3,6];

function Quick(arr) {

  

  const len = arr.length;

  

  if(len == 0)

    return [];

  

  let left = [];

  let right = [];

  const pivot = arr[0];

  

  for(let i=1; i<len; i++) {

    if(arr[i] < pivot)

      left.push(arr[i]);

    else

      right.push(arr[i]);

  }

  return Quick(left).concat(pivot, Quick(right));

}

console.log(Quick(arr));

2. pivot값이 중간 값인 경우

let arr = [1,4,5,2,3,6];

function Quick(arr) {

  

  const len = arr.length;

  

  if(len == 0)

    return [];

  

  let left = [];

  let right = [];

  const tmp = arr[0];

  arr[0] = arr[parseInt(len/2)];

  arr[parseInt(len/2)] = tmp;

  

  const pivot = arr[0];

  

  for(let i=1; i<len; i++) {

    if(arr[i] < pivot)

      left.push(arr[i]);

    else

      right.push(arr[i]);

  }

  return Quick(left).concat(pivot, Quick(right));

}

console.log(Quick(arr));