자바스크립트 정렬 알고리즘 6 : Quick Sort

*Udemy의 "Master the Coding Interview : Data Structures + Algorithms" 강의에서 학습한 내용을 정리한 포스팅입니다.

*자바스크립트를 배우는 단계라 오류가 있을 수 있습니다. 틀린 내용은 댓글로 말씀해주시면 수정하겠습니다. 감사합니다. :)

---

Quick Sort는 Merge Sort보다 직접 구현하기가 더 복잡하다. Quick Sort 또한 Divide and Conquer 개념을 사용하고, 동시에 Pivoting 개념을 활용한다.

 

Quick Sort는 공간복잡도가 O(log n)으로 Merge Sort의 O(n)보다 메모리 효율성이 높은 알고리즘이다. 하지만 주의할 점은, worst 케이스의 경우 시간복잡도가 O(n^2)가 될 수 있다는 점이다. 특히 어느 정도 정렬이 되어 있는 데이터에서 가장 작은, 또는 가장 큰 element를 pivoting할 대상으로 선정할 경우, 사실상 거의 divide and conquer가 이뤄지지 않기 때문에 O(n^2)가 되는 것이다.

 

따라서 데이터에서 적절한 element를 pivot으로 고를 수 있다면, Merge Sort만큼의 속도와 더불어 더 나은 공간복잡도로 더 효율적인 정렬을 할 수 있다. (worst 케이스를 제외하더라도, 평균적으로 Quick Sort의 속도가 가장 빠르다고 한다.)

 

☞ Quick Sort 로직

 

const numbers = [99, 44, 6, 2, 1, 5, 63, 87, 283, 4, 0];

function quickSort(array, left, right){
  const len = array.length; 
  let pivot;
  let partitionIndex;

  if(left < right) {
    pivot = right;
    partitionIndex = partition(array, pivot, left, right);
    
    //sort left and right
    quickSort(array, left, partitionIndex - 1);
    quickSort(array, partitionIndex + 1, right);
  }
  return array;
}
   
function partition(array, pivot, left, right){
  let pivotValue = array[pivot];
  let partitionIndex = left;

  for(let i = left; i < right; i++) {
    if(array[i] < pivotValue){
      swap(array, i, partitionIndex);
      partitionIndex++;
    }
  }
  swap(array, right, partitionIndex);
  return partitionIndex;
}

function swap(array, firstIndex, secondIndex){
    var temp = array[firstIndex];
    array[firstIndex] = array[secondIndex];
    array[secondIndex] = temp;
}

//Select first and last index as 2nd and 3rd parameters
quickSort(numbers, 0, numbers.length - 1);
console.log(numbers);