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

কুইক সোর্ট

কুইক সোর্ট জাভাস্ক্রিপ্টে সবচেয়ে গুরুত্বপূর্ণ সর্টিং মেথডের একটিই। এটি অ্যারে থেকে একটি পিভট ভ্যালু (র‍্যান্ডম ভ্যালু) নেয়। অ্যারে-এর বাকি সব এলিমেন্ট দুটি ক্যাটাগরিতে ভাগ হয়: পিভট থেকে ছোট এবং পিভট থেকে বড়।

তারপর প্রতিটি ক্যাটাগরির জন্য একই প্রক্রিয়া दुहरায়: নতুন পিভট বেছে নেয়া, সাব-ক্যাটাগরি তৈরি করা। 最終ভাবে সাব-ক্যাটাগরিগুলো এমনভাবে ভাগ হয় যে প্রতিটিতে এক বা শূন্য এলিমেন্ট থাকে। বাকি ভ্যালুগুলো পূর্বের পিভট পয়েন্টে থাকে।

উদাহরণ

<html> <body> 
<script> 
  function quickSort(originalArr) {
    if (originalArr.length <= 1) {
      return originalArr;
    } else {
      var leftArr = [];
      var rightArr = [];
      var newArr = [];
      var pivot = originalArr.pop(); // পিভট ভ্যালু নেওয়া
      var length = originalArr.length;
      
      for (var i = 0; i < length; i++) {
        if (originalArr[i] <= pivot) {
          leftArr.push(originalArr[i]);
        } else {
          rightArr.push(originalArr[i]);
        }
      }
      return newArr.concat(quickSort(leftArr), pivot, quickSort(rightArr));
    }
  }
  
  var myArray = [9, 0, 2, 7, -2, 6, 1];
  document.write("Original array: " + myArray);
  var sortedArray = quickSort(myArray);
  document.write("Sorted array: " + sortedArray);
</script> 
</body> </html>

আউটপুট

Original array: 9,0,2,7,-2,6,1 Sorted array: -2,0,1,2,6,7,9

ব্যাখ্যা

এই ইমপ্লিমেন্টেশন শেষ এলিমেন্টকে পিভট হিসেবে নেয়। pop() দিয়ে পিভট সরিয়ে বাকি এলিমেন্টগুলো পিভটের সাথে তুলনা করে leftArr এবং rightArr-এ ভাগ করে। তারপর রিকার্সিভলি লেফ্ট এবং রাইট সাব-অ্যারে সর্ট করে কনক্যাট করে।