JavaScript Quicksort เรียกซ้ำ

เราจำเป็นต้องเขียนฟังก์ชัน JavaScript ที่ใช้อาร์เรย์ของ Numbers ฟังก์ชันควรใช้อัลกอริธึมของ quicksort เพื่อจัดเรียงอาร์เรย์ในลำดับที่เพิ่มขึ้นหรือลดลง

อัลกอริธึม QuickSort

Quicksort ทำตามขั้นตอนด้านล่าง -

ขั้นตอนที่ 1 − สร้างองค์ประกอบใด ๆ เป็นเดือย (ควรเป็นอันดับแรกหรือสุดท้าย แต่องค์ประกอบใด ๆ สามารถเป็นเดือยได้)

ขั้นตอนที่ 2 − แบ่งอาร์เรย์ตามจุดหมุน

ขั้นตอนที่ 3 − ใช้การเรียงลำดับอย่างรวดเร็วบนพาร์ติชั่นด้านซ้ายซ้ำๆ

ขั้นตอนที่ 4 − ใช้การเรียงลำดับอย่างรวดเร็วบนพาร์ติชั่นด้านขวาซ้ำๆ

ความซับซ้อนของเวลาเฉลี่ยและกรณีที่ดีที่สุดของ QuickSort คือ O(nlogn) ในขณะที่ในกรณีที่เลวร้ายที่สุด ความซับซ้อนของ QuickSort อาจทำให้ช้าลงได้ถึง 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 ]