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

মার্জ সর্ট হল ডিভাইড অ্যান্ড কনক্যুয়ার টেকনিকের উপর ভিত্তি করে সাজানোর কৌশল। এটির Ο(n log n) এর সবচেয়ে খারাপ-কেস সময়ের জটিলতা রয়েছে। তবে এটি স্থানের পরিপ্রেক্ষিতে একটি অতিরিক্ত খরচের সাথে আসে কারণ এই অ্যালগরিদমটি একটি অতিরিক্ত O(n) মেমরি নেয়।

এখন দেখা যাক কিভাবে আমরা এই অ্যালগরিদম বাস্তবায়ন করতে যাচ্ছি। আমরা 2টি ফাংশন তৈরি করব, একত্রিত করব এবং একত্রিত করব।

একত্রিত করুন − এই ফাংশনটি 2টি আর্গুমেন্ট নেয়, এগুলি হল 2টি আংশিক অ্যারে যা এটি সঠিক ক্রমে উপাদান সন্নিবেশ করার মাধ্যমে একটিতে সংযুক্ত করে৷

একত্রীকরণ সাজান − এই ফাংশনটি পুনরাবৃত্তিমূলকভাবে অ্যারের বাম এবং ডান অংশে মার্জসোর্টকে কল করে এবং তারপর এই অ্যারের অংশগুলিকে একত্রিত করতে মার্জ ব্যবহার করে। আমরা বাস্তবায়নের দিকে তাকালে এটি আরও স্পষ্ট হবে৷

মার্জ ফাংশন দিয়ে শুরু করা যাক এবং সরাসরি কোড −

উদাহরণ

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]

এখন আমরা আমাদের মার্জসর্ট ফাংশনে এই ফাংশনটি আসলে পুরো অ্যারে সাজানোর জন্য ব্যবহার করব।

আমরা মার্জসোর্টের জন্য একটি অভ্যন্তরীণ ফাংশন তৈরি করব যা আমরা আমাদের তুলনাকারীকে উপলব্ধ করার জন্য একটি বাইরের ফাংশন দিয়ে মোড়ানো করব যাতে আমাদের ফাংশনটি এক্সটেনসিবল হয়। আসুন এই অভ্যন্তরীণ ফাংশনটি দেখুন -

উদাহরণ

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 }
]

দ্রুত সাজান

কুইক সর্ট হল একটি অত্যন্ত দক্ষ বাছাই করার অ্যালগরিদম এবং এটি ডেটা অ্যারেকে ছোট অ্যারেগুলিতে বিভাজনের উপর ভিত্তি করে। একটি বড় অ্যারেকে দুটি অ্যারেতে বিভক্ত করা হয় যার মধ্যে একটি নির্দিষ্ট মানের থেকে ছোট মান ধারণ করে, পিভট বলুন, যার উপর ভিত্তি করে পার্টিশন তৈরি করা হয় এবং অন্য একটি অ্যারে পিভট মানের থেকে বেশি মান ধারণ করে।

একটি অ্যারেকে দ্রুত বাছাই পার্টিশন করে এবং তারপরে দুটি ফলস্বরূপ সাবয়ারে সাজানোর জন্য নিজেকে দুবার পুনরাবৃত্তি করে। এই অ্যালগরিদমটি বড় আকারের ডেটা সেটের জন্য যথেষ্ট দক্ষ কারণ এর গড় এবং সবচেয়ে খারাপ ক্ষেত্রে জটিলতা হল Ο(n2), যেখানে n হল আইটেমের সংখ্যা৷

পার্টিশন প্রক্রিয়া

নিম্নলিখিত অ্যানিমেটেড উপস্থাপনা ব্যাখ্যা করে যে কীভাবে একটি অ্যারেতে পিভট মান খুঁজে পাওয়া যায়।https://www.tutorialspoint.com/data_structures_algorithms/images/quick_sort_partition_animation.gif

পিভট মান তালিকাটিকে দুটি ভাগে ভাগ করে। এবং পুনরাবৃত্তভাবে, আমরা প্রতিটি উপ-তালিকার জন্য পিভট খুঁজে পাই যতক্ষণ না সমস্ত তালিকায় শুধুমাত্র একটি উপাদান থাকে।

বিভাজনে আমরা যা করি তা হল আমরা অ্যারে থেকে প্রথম উপাদানটি নির্বাচন করি (এলোমেলোভাবে এলোমেলো উপাদানগুলি) এবং তারপর এই উপাদানটির সাথে বাকি অ্যারের তুলনা করি। তারপরে আমরা এই উপাদানের চেয়ে কম সমস্ত উপাদানগুলিকে পিভট সূচকের বাম দিকে এবং এর চেয়ে বড় মানগুলিকে পিভট সূচকের ডানদিকে নিয়ে যাই। সুতরাং যখন আমরা শেষ পর্যন্ত পৌঁছাই, তখন পিভট উপাদান (প্রথম উপাদান) তার সঠিক অবস্থানে স্থাপন করা হয়।

কারণ এর চেয়ে বড় সমস্ত উপাদান ডানদিকে এবং তার চেয়ে কম বাম দিকে এই উপাদানটিকে সঠিক জায়গায় রেখে দেয়। আমরা এই বিভাজন প্রক্রিয়াটি প্রসারিত করি যাতে বাম এবং ডান সাব অ্যারেতে পার্টিশনকে বারবার কল করে সাজাতে সাহায্য করা যায়।

আমরা পার্টিশন ফাংশনটি নিম্নরূপ প্রয়োগ করতে পারি -

উদাহরণ

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 উপাদানের বেশি একটি উইন্ডো থাকে, তাহলে আমরা অ্যারেতে নিম্ন থেকে উচ্চ পর্যন্ত পার্টিশনকে কল করি, প্রত্যাবর্তিত সূচকটি গ্রহণ করি এবং অ্যারের বাম এবং ডান অংশে কুইকসর্ট কল করতে এটি ব্যবহার করি৷

উদাহরণ

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 ]