QuickSort를 구현하기 위해 JavaScript에서 분할 및 정복 논리 구현

숫자 배열을 가져와서 빠른 정렬 알고리즘을 사용하여 정렬하는 JavaScript 함수를 작성해야 합니다.

빠른 정렬

이 알고리즘은 기본적으로 루프의 모든 패스에서 피벗을 선택하고 피벗보다 작은 모든 요소를 ​​왼쪽에, 피벗보다 큰 모든 요소를 ​​오른쪽에 배치하는 분할 정복 알고리즘입니다(오름차순 정렬이 반대인 경우)

예시

이 함수의 코드를 작성해 봅시다 -

const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
// Find a "pivot" element in the array to compare all other
// elements against and then shift elements before or after
// pivot depending on their values
const quickSort = (arr, left = 0, right = arr.length - 1) => {
   let len = arr.length, index;
   if(len > 1) {
      index = partition(arr, left, right)
      if(left < index - 1) {
         quickSort(arr, left, index - 1)
      }
      if(index < right) {
         quickSort(arr, index, right)
      }
   }
   return arr
}
const partition = (arr, left, right) => {
   let middle = Math.floor((right + left) / 2),
   pivot = arr[middle],
   i = left, // Start pointer at the first item in the
   array
   j = right // Start pointer at the last item in the array
   while(i <= j) {
      // Move left pointer to the right until the value at the
      // left is greater than the pivot value
      while(arr[i] < pivot) {
         i++
      }
      // Move right pointer to the left until the value at the
      // right is less than the pivot value
      while(arr[j] > pivot) {
         j--
      }
      // If the left pointer is less than or equal to the
      // right pointer, then swap values
      if(i <= j) {
         [arr[i], arr[j]] = [arr[j], arr[i]] // ES6 destructuring swap
         i++
         j--
      }
   }
   return i
}
console.log(quickSort(arr));

출력

콘솔의 출력 -

[
   2,   3,    4,  6, 23,
   23,  34,   34, 43, 54,
   54, 232, 3434
]