ผสานการเรียงลำดับกับการเรียงลำดับอย่างรวดเร็วใน Javascript

Merge sort เป็นเทคนิคการจัดเรียงตามเทคนิคการแบ่งและพิชิต ความซับซ้อนของเวลากรณีที่เลวร้ายที่สุดคือ Ο(n log n) แต่สิ่งนี้มาพร้อมกับค่าใช้จ่ายเพิ่มเติมในแง่ของพื้นที่เนื่องจากอัลกอริธึมนี้ใช้หน่วยความจำ O(n) พิเศษ

ทีนี้มาดูว่าเราจะใช้อัลกอริทึมนี้อย่างไร เราจะสร้าง 2 ฟังก์ชัน mergeSort และ merge

ผสาน − ฟังก์ชันนี้รับ 2 อาร์กิวเมนต์ ซึ่งเป็น 2 อาร์เรย์บางส่วน จากนั้นจะรวมเป็นหนึ่งเดียวโดยการแทรกองค์ประกอบในลำดับที่ถูกต้อง

ผสานการเรียงลำดับ − ฟังก์ชันนี้เรียก mergeSort ซ้ำๆ ที่ครึ่งซ้ายและขวาของอาร์เรย์ จากนั้นใช้การผสานเพื่อรวมส่วนต่างๆ ของอาร์เรย์เหล่านี้เข้าด้วยกัน สิ่งนี้จะชัดเจนขึ้นมากเมื่อเราดูที่การนำไปใช้

มาเริ่มกันที่ฟังก์ชันผสานและดำดิ่งลงไปที่โค้ด −

ตัวอย่าง

function merge(left, right) {
   let mergedArr = [];
   let i = 0;
   let j = 0;
   // Try merging till we reach end of either one of the arrays.
   while (i < left.length && j < right.length) {
      if (compare(left[i], right[j])) {
         mergedArr.push(left[i]);
         i++;
      } else {
         mergedArr.push(right[j]);
         j++;
      }
   }
   // If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
   // the for loop above would stop once it reaches the end of
   // The left array leaving 3 elements in the right array
   // In order to add the remaining elements from either array,
   // We need to add elements from i to end in left and j to end
   // in the right array to the merged array.
   return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}

ฟังก์ชันนี้จะนำอาร์เรย์ที่เรียงลำดับแล้ว 2 อันมารวมกันเป็นเวลา O(n) เพื่อให้ยังคงเรียงลำดับเป็นอาร์เรย์ที่ใหญ่กว่า อ้างถึงความคิดเห็นของรหัสสำหรับคำอธิบายเชิงลึกของวิธีการ คุณสามารถทดสอบสิ่งนี้โดยใช้ −

ตัวอย่าง

let a1 = [1, 2, 3, 5]
let a2 = [4, 6, 8, 9]
console.log(merge(a1, a2))

ผลลัพธ์

[1, 2, 3, 4, 5, 8, 9]

ตอนนี้เราจะใช้ฟังก์ชันนี้ในฟังก์ชัน mergesort เพื่อจัดเรียงอาร์เรย์ทั้งหมด

เราจะสร้างฟังก์ชันภายในสำหรับ mergeSort ซึ่งเราจะห่อด้วยฟังก์ชันภายนอกเพื่อให้ตัวเปรียบเทียบของเราพร้อมใช้งาน เพื่อให้ฟังก์ชันของเราสามารถขยายได้ มาดูฟังก์ชันภายในกัน −

ตัวอย่าง

function mergeSortInner(arr) {
   if (arr.length < 2) {
      return arr;
   }
   let mid = Math.floor(arr.length / 2);
   // Create an array from 0 to mid - 1 elements
   let left = arr.slice(0, mid);
   // Create an array from mid to the last element
   let right = arr.slice(mid);
   // Sort the left half, sort the right half,
   // merge the sorted arrays and return
   return merge(mergeSortInner(left), mergeSortInner(right));
}

ฟังก์ชันนี้แยกอาร์เรย์ออกเป็นสองส่วน จัดเรียงทีละรายการ จากนั้นส่งคืนอาร์เรย์ที่ผสานกลับ

ให้เราดูโค้ดที่สมบูรณ์พร้อมการทดสอบ -

ตัวอย่าง

function mergeSort(arr, compare = (a, b) => a < b) {
   function merge(left, right) {
      let mergedArr = [];
      let i = 0;
      let j = 0;
      // Try merging till we reach end of either one of the arrays.
      while (i < left.length && j < right.length) {
         if (compare(left[i], right[j])) {
            mergedArr.push(left[i]);
            i++;
         } else {
            mergedArr.push(right[j]);
            j++;
         }
      }
      // If left was 1, 2, 3, 5 and right was 4, 6, 7, 9
      // the for loop above would stop once it reaches the end of
      // The left array leaving 3 elements in the right array
      // In order to add the remaining elements from either array,
      // We need to add elements from i to end in left and j to end
      // in the right array to the merged array.
      return mergedArr.concat(left.slice(i)).concat(right.slice(j));
   }
   function mergeSortInner(arr) {
      if (arr.length < 2) {
         return arr;
      }
      let mid = Math.floor(arr.length / 2);
      let left = arr.slice(0, mid);
      let right = arr.slice(mid);
      return merge(mergeSortInner(left), mergeSortInner(right));
   }
   // Call inner mergesort to sort and return the array for us.
   return mergeSortInner(arr);
}
You can test this using:
let arr = [5, 8, 9, 12, -8, 31, 2];
// Sort Array elements in increasing order
arr = mergeSort(arr);
console.log(arr);
// Sort Array elements in decreasing order
arr = mergeSort(arr, (a, b) => a > b);
console.log(arr);
arr = [
   {
      name: "Harry",
      age: 20
   },
   {
      name: "Jacob",
      age: 25
   },
   {
      name: "Mary",
      age: 12
   }
];
// Sort Array elements in increasing order alphabetically by names
arr = mergeSort(arr, (a, b) => a.name < b.name);
console.log(arr);
// Sort Array elements in decreasing order of ages
arr = mergeSort(arr, (a, b) => a.age < b.age);
console.log(arr);

ผลลัพธ์

[ -8, 2, 5, 8, 9, 12, 31 ]
[ 31, 12, 9, 8, 5, 2, -8 ]
[
   { name: 'Harry', age: 20 },
   { name: 'Jacob', age: 25 },
   { name: 'Mary', age: 12 }
]
[
   { name: 'Mary', age: 12 },
   { name: 'Harry', age: 20 },
   { name: 'Jacob', age: 25 }
]

การเรียงลำดับอย่างรวดเร็ว

การเรียงลำดับอย่างรวดเร็วเป็นอัลกอริธึมการเรียงลำดับที่มีประสิทธิภาพสูง และขึ้นอยู่กับการแบ่งพาร์ติชั่นของอาร์เรย์ของข้อมูลออกเป็นอาร์เรย์ที่เล็กกว่า อาร์เรย์ขนาดใหญ่แบ่งออกเป็นสองอาร์เรย์ โดยที่อาร์เรย์หนึ่งเก็บค่าที่น้อยกว่าค่าที่ระบุ เช่น pivot โดยอิงตามพาร์ติชั่นที่สร้างขึ้น และอาร์เรย์อื่นจะเก็บค่าที่มากกว่าค่าเดือย

การเรียงลำดับอย่างรวดเร็วแบ่งพาร์ติชั่นอาร์เรย์แล้วเรียกตัวเองซ้ำสองครั้งเพื่อเรียงลำดับอาร์เรย์ย่อยที่เป็นผลลัพธ์ทั้งสอง อัลกอริธึมนี้ค่อนข้างมีประสิทธิภาพสำหรับชุดข้อมูลขนาดใหญ่ เนื่องจากความซับซ้อนของค่าเฉลี่ยและกรณีที่เลวร้ายที่สุดคือ Ο(n2) โดยที่ n คือจำนวนรายการ

กระบวนการแบ่งพาร์ติชั่น

การแสดงภาพเคลื่อนไหวต่อไปนี้จะอธิบายวิธีค้นหาค่า pivot ในอาร์เรย์https://www.tutorialspoint.com/data_structures_algorithms/images/quick_sort_partition_animation.gif

ค่าเดือยแบ่งรายการออกเป็นสองส่วน และแบบเรียกซ้ำ เราจะพบจุดหมุนสำหรับรายการย่อยแต่ละรายการจนกว่ารายการทั้งหมดจะมีเพียงองค์ประกอบเดียว

สิ่งที่เราทำในการแบ่งพาร์ติชั่นคือเราเลือกองค์ประกอบแรกจากอาร์เรย์ (องค์ประกอบแบบสุ่มในการเรียงลำดับอย่างรวดเร็วแบบสุ่ม) จากนั้นเปรียบเทียบส่วนที่เหลือของอาร์เรย์กับองค์ประกอบนี้ จากนั้นเราจะย้ายองค์ประกอบทั้งหมดที่น้อยกว่าองค์ประกอบนี้ไปทางด้านซ้ายของสิ่งที่เราเรียกว่าดัชนี pivot และค่าที่มากกว่านี้ไปทางด้านขวาของดัชนี pivot ดังนั้นเมื่อเราถึงจุดสิ้นสุด องค์ประกอบ pivot (องค์ประกอบแรก) จะถูกวางในตำแหน่งที่ถูกต้อง

ทั้งนี้เนื่องจากองค์ประกอบทั้งหมดที่มากกว่าทางด้านขวาและน้อยกว่าทางด้านซ้าย ทำให้องค์ประกอบนี้อยู่ในตำแหน่งที่ถูกต้อง เราขยายกระบวนการแบ่งพาร์ติชั่นนี้เพื่อช่วยเราในการเรียงลำดับโดยการเรียกพาร์ติชั่นซ้ำๆ บนอาร์เรย์ย่อยด้านซ้ายและขวา

เราสามารถใช้ฟังก์ชันพาร์ทิชันได้ดังนี้ -

ตัวอย่าง

function partition(arr, low, high, compare) {
   let pivotIndex = low + 1;
   for (let i = pivotIndex; i < high; i++) {
      if (compare(arr[i], arr[low])) {
      // Swap the number less than the pivot
      swap(arr, i, pivotIndex);
      pivotIndex += 1;
      }
   }
   // Place the pivot to its correct position
   swap(arr, pivotIndex - 1, low);
   // Return pivot's position
   return pivotIndex - 1;
}
function swap(arr, i, j) {
   let temp = arr[i];
   arr[i] = arr[j];
   arr[j] = temp;
}
You can test the partition function using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
console.log(partition(arr, 0, arr.length, (l, r) => l < r));
console.log(arr);

ผลลัพธ์

4
[ -6, 1, 3, 2, 5, 10, 8, 45, 9 ]

โปรดทราบว่าองค์ประกอบทางซ้ายของ 5 มีค่าน้อยกว่า 5 และองค์ประกอบทางขวามากกว่า 5 เรายังเห็นว่าดัชนีของ 5 คือ 4

ตอนนี้เรามาดูกันว่า Quick Sort ทำงานอย่างไร -

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

ตัวอย่าง

function QuickSort(arr, low, high, compare = (l, r) => l < r) {
   if (high - low > 0) {
      // Partition the array
      let mid = partition(arr, low, high, compare);
      // Recursively sort the left half
      QuickSort(arr, low, mid, compare);
      // Recursively sort the right half
      QuickSort(arr, mid + 1, high, compare);
   }
}
You can test this using:
let arr = [5, 1, 10, 8, 9, 3, 2, 45, -6];
QuickSort(arr, 0, arr.length, (l, r) => l < r);
console.log(arr);

ผลลัพธ์

[ -6, 1, 2, 3, 5, 8, 9, 10, 45 ]