JavaScript Quicksort แบบเรียกซ้ำ (Recursive)

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

อัลกอริทึม QuickSort

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

ขั้นตอนที่ 1 - ทำให้สมาชิกใดสมาชิกหนึ่งเป็น pivot (แนะนำให้เป็นตัวแรกหรือตัวสุดท้าย แต่สมาชิกไหนก็ได้)

ขั้นตอนที่ 2 - แบ่งพาร์ติชันอาร์เรย์ตาม pivot

ขั้นตอนที่ 3 - ใช้ quick sort กับพาร์ติชันซ้ายแบบเรียกซ้ำ

ขั้นตอนที่ 4 - ใช้ quick sort กับพาร์ติชันขวาแบบเรียกซ้ำ

ความซับซ้อนของเวลาเฉลี่ยและกรณีที่ดีที่สุดของ 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); //สลับสองสมาชิก
      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 ]