자바스크립트 퀵소트 재귀

Numbers 배열을 취하는 JavaScript 함수를 작성해야 합니다. 이 함수는 배열을 오름차순 또는 내림차순으로 정렬하기 위해 퀵소트 알고리즘을 적용해야 합니다.

퀵 정렬 알고리즘

Quicksort는 다음 단계를 따릅니다. −

1단계 − 모든 요소를 ​​피벗으로 만듭니다(첫 번째 또는 마지막이 바람직하지만 모든 요소가 피벗이 될 수 있음).

2단계 − 피벗을 기준으로 배열을 분할합니다.

3단계 − 왼쪽 파티션에 재귀적으로 퀵 정렬 적용

4단계 − 올바른 파티션에 재귀적으로 퀵 정렬 적용

QuickSort의 평균 및 최상의 시간 복잡도는 O(nlogn)인 반면 최악의 경우 O(n^2)까지 느려질 수 있습니다.

예시

이에 대한 코드는 -

const arr = [5,3,7,6,2,9];
const swap = (arr, leftIndex, rightIndex) => {
   let temp = arr[leftIndex];
   arr[leftIndex] = arr[rightIndex];
   arr[rightIndex] = temp;
};
const partition = (arr, left, right) => {
   let pivot = arr[Math.floor((right + left) / 2)];
   let i = left;
   let j = right;
   while (i <= j) {
      while (arr[i] < pivot) {
         i++;
      };
      while (arr[j] > pivot) {
         j--;
      };
      if (i <= j) {
         swap(arr, i, j); //sawpping two elements
         i++;
         j--;
      };
   };
   return i;
}
const quickSort = (arr, left = 0, right = arr.length - 1) => {
   let index;
   if (arr.length > 1) {
      index = partition(arr, left, right);
      if (left < index - 1) {
         quickSort(arr, left, index - 1);
      };
      if (index < right) {
         quickSort(arr, index, right);
      };
   }
   return arr;
}
let sortedArray = quickSort(arr);
console.log(sortedArray);

출력

콘솔의 출력은 -

[ 2, 3, 5, 6, 7, 9 ]