본문 바로가기
Computer Science/Algorithm, Data Structure

자바스크립트 알고리즘 퀵 정렬(Quick Sort)

by Write and Remember 2019. 6. 16.

출처: https://reactgo.com/quicksort-algorithm-javascript/

 

Quick Sort(퀵 정렬)에 대하여 알아보자.

 

병합 정렬(Merge Sort) 및 힙 정렬(Heap Sort)보다 

 

빠르게 수행되는 큰 데이터 세트의 효율적인 정렬 알고리즘이다.

 

배열의 임의의 기준 값을 pivot, 피벗보다 작으면 왼쪽, 크면 오른쪽으로 이동하여 정렬한다.

 

여기서는 피벗의 기준을 배열의 마지막으로 잡고

 

피벗보다 작으면 left 배열로 추가

 

크면 right 배열에 값을 추가한다.

 

위에서 했던 방법을 왼쪽, 오른쪽 부분에서 재귀적으로 실행하고

 

그다음 전개 연산자(spread operator)로 left, pivot, right

 

합친 후 리턴한다.

 

function quickSort(arr, length = arr.length - 1, start = 0) {
  if(arr.length < 2) return arr 
  // pivot value(배열의 끝을 기준)
  const pivot = arr[arr.length - 1] 
  const left = [];
  const right = [];

  while(start < length){
    // 피벗의 값보다 작으면 left 배열에 값을 추가
    if(arr[start] < pivot) left.push(arr[start])
    // 아니면 오른쪽 배열에 값을 추가
    else right.push(arr[start])
    start++
  }

  return [...quickSort(left), pivot, ...quickSort(right)]
}

console.log(quickSort([4,5,3,6,2,1,9])) // [1, 2, 3, 4, 5, 6, 9]

댓글0