[알고리즘] Quick sort

function quickSort(a) {
  if (a.length < 2) {
    return a
  }
  var pivot = a[0] // 첫번째 요소를 pivot으로 세팅
  var left = []
  var center = [pivot]
  var right = []
  for (var i = 1; i < a.length; i++) {
    if (a[i] > pivot) {
      right.push(a[i])
    } else if (a[i] === pivot) {
      center.push(a[i])
    } else {
      left.push(a[i])
    }
  }
  return [...quickSort(left), ...center, ...quickSort(right)]
}

quickSort([7, 4, 9, 8, 5, 3, 2, 1, 9, 3])
/*
[1, 2, 3, 3, 4, 5, 7, 8, 9, 9]
*/

function swap(arr, i1, i2){
    var tmp = arr[i1];
    arr[i1] = arr[i2];
    arr[i2] = tmp;
}

// partition 은 pivot 을 기준으로 배열을 양분한다
function partition(a, left, right){
    var pivot = a[left];   // 첫번째 요소를 pivot으로 세팅
    var i = left;
    var j = right;

    while(i < j){
        while(pivot < a[j]) j--;    // 오른쪽끝부터 왼쪽으로 pivot 보다 작거나 같은 값의 위치를 찾는다
        while(i<j && a[i] <= pivot) i++;    // 왼쪽끝부터 오른쪽으로 pivot보다 큰값의 위치를 찾는다
        swap(a, i, j);      // 두 값을 교환
    }
    swap(a, left, i);   // swap 결과 i 위치를 기준으로 왼쪽은 모두 pivot 보다 작거나 같은 값이 되고, 오른쪽은 pivot보다 큰 값이 위치하게 된다

    log(pivot, left, right, a); // pivot 으로 양분된 결과 출력
    return i;   // pivot 의 위치를 리턴
}

function log(pivot, left, right, a){
    var head = "x".repeat(left).split("");
    var body = a.slice(left, right+1);
    var tail = "x".repeat(a.length-1-right).split("");
    console.log("p(" + pivot + ") => " + [...head, ...body, ...tail]);    
}

function quickSort(a, left=0, right=a.length-1){
    if(left >= right){
        return;
    }

    var i = partition(a, left, right);

    quickSort(a, left, i-1);
    quickSort(a, i+1, right);
}
var arr = [4,5,7,5,4,2,6,0,8,3,1,3,9];
quickSort(arr);
console.log(arr);