ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 자바스크립트 알고리즘 퀵 정렬(Quick Sort)
    Computer Science/Algorithm, Data Structure 2019.06.16 16:02

    출처: 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