জাভাস্ক্রিপ্ট কুইকসোর্ট রিকার্সিভ

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

দ্রুত সাজানোর অ্যালগরিদম

Quicksort নিচের ধাপগুলো অনুসরণ করে −

ধাপ 1 − যে কোনো উপাদানকে পিভট হিসেবে তৈরি করুন (প্রথম বা শেষ, তবে যেকোনো উপাদানই পিভট হতে পারে)

ধাপ 2 − পিভটের ভিত্তিতে অ্যারেকে বিভাজন করুন

ধাপ 3 − বারবার বাম পার্টিশনে একটি দ্রুত বাছাই প্রয়োগ করুন

পদক্ষেপ 4৷ − ডান পার্টিশনে পুনরাবৃত্তভাবে একটি দ্রুত বাছাই প্রয়োগ করুন

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); //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 ]