জাভাস্ক্রিপ্টে মার্জ সোর্ট বনাম কুইক সোর্ট

মার্জ সোর্ট একটি সর্টিং টেকনিক যা ডিভাইড এন্ড কনকোয়ার (divide and conquer) টেকনিকের উপর ভিত্তি করে। এর ওয়ার্স্ট-কেস টাইম কমপ্লেক্সিটি O(n log n)। কিন্তু এর জন্য এক্সট্রা O(n) মেমোরি লাগে।

মার্জ সোর্ট ইমপ্লিমেন্টেশন

দুটি ফাংশন তৈরি করব: mergeSort এবং merge।

• merge - এই ফাংশন ২টি আর্গুমেন্ট নেয় (দুটি পার্শিয়াল অ্যারে), সেগুলোকে সঠিক ক্রমে ইন্সার্ট করে একটা বড় অ্যারেতে কনক্যাট করে।
• mergeSort - এই ফাংশন রিকার্সিভলি বাম এবং ডান হälfteর ওপর mergeSort কল করে, তারপর merge দিয়ে সেগুলো কম্বাইন করে।

merge ফাংশন

function merge(left, right) {
  let mergedArr = [];
  let i = 0, j = 0;
  while (i < left.length && j < right.length) {
    if (compare(left[i], right[j])) {
      mergedArr.push(left[i]);
      i++;
    } else {
      mergedArr.push(right[j]);
      j++;
    }
  }
  return mergedArr.concat(left.slice(i)).concat(right.slice(j));
}

mergeSort ফাংশন

function mergeSort(arr, compare = (a, b) => a < b) {
  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));
  }
  return mergeSortInner(arr);
}

টেস্ট কেস

let arr = [5, 8, 9, 12, -8, 31, 2];
arr = mergeSort(arr); // ascending
console.log(arr); // [-8, 2, 5, 8, 9, 12, 31]

arr = mergeSort(arr, (a, b) => a > b); // descending
console.log(arr); // [31, 12, 9, 8, 5, 2, -8]

কুইক সোর্ট

কুইক সোর্ট একটি হাইলি ইফিশিয়েন্ট সর্টিং অ্যালগরিদম যা অ্যারে পার্টিশনিং på ভিত্তি করে। বড় অ্যারেকে দুটি ছোট অ্যারেতে পার্টিশন করে: একটি পিভট থেকে ছোট ভ্যালুগুলোর, অন্যটি পিভট থেকে বড় ভ্যালুগুলোর।

পার্টিশন প্রসেস

function partition(arr, low, high, compare) {
  let pivotIndex = low + 1;
  for (let i = pivotIndex; i < high; i++) {
    if (compare(arr[i], arr[low])) {
      swap(arr, i, pivotIndex);
      pivotIndex += 1;
    }
  }
  swap(arr, pivotIndex - 1, low);
  return pivotIndex - 1;
}

function swap(arr, i, j) {
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

QuickSort ফাংশন

function QuickSort(arr, low, high, compare = (l, r) => l < r) {
  if (high - low > 0) {
    let mid = partition(arr, low, high, compare);
    QuickSort(arr, low, mid, compare);
    QuickSort(arr, mid + 1, high, compare);
  }
}

টেস্ট

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]

তুলনা

জাভাস্ক্রিপ্টের বিল্ট-ইন Array.sort() ভিন্ন ব্রাউজার エンজিনে ভিন্ন অ্যালগরিদম ব্যবহার করে (SpiderMonkey: mergeSort, V8: Timsort/QuickSort হাইব্রিড)।