JavaScript Quicksort đệ quy

Chúng tôi được yêu cầu viết một hàm JavaScript có trong một mảng Số. Hàm nên áp dụng thuật toán quicksort để sắp xếp mảng theo thứ tự tăng hoặc giảm.

Thuật toán sắp xếp nhanh

Quicksort thực hiện theo các bước sau -

Bước 1 - Đặt bất kỳ phần tử nào làm trục xoay (tốt nhất là đầu tiên hoặc cuối cùng, nhưng bất kỳ phần tử nào cũng có thể là trục xoay)

Bước 2 - Phân vùng mảng trên cơ sở pivot

Bước 3 - Áp dụng một cách nhanh chóng cho phân vùng bên trái một cách đệ quy

Bước 4 - Áp dụng một cách nhanh chóng cho phân vùng bên phải một cách đệ quy

Độ phức tạp thời gian xử lý trường hợp trung bình và tốt nhất của QuickSort là O (nlogn) trong khi trong trường hợp xấu nhất, nó có thể làm chậm lên đến O (n ^ 2).

Ví dụ

Mã cho điều này sẽ là -

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);

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

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