কুইক সোর্ট বাস্তবায়ন (Divide & Conquer) - JavaScript

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

অ্যালগরিদম ধাপ

1. পিভট বেছে নিন (মাঝপথি, প্রথম, শেষ, বা র‍্যান্ডম)
2. পার্টিশন: পিভট থেকে ছোট বামে, বড় ডানে
3. রিকার্সিভ: বাম এবং ডান সাব-অ্যারে সোর্ট করুন
4. বেস কেস: ০ বা ১ উপাদান বালে সোর্টেড

বাস্তবায়ন

const quickSort = (arr, left = 0, right = arr.length - 1) => {
  if (left >= right) return arr; // বেস কেস
  
  const index = partition(arr, left, right);
  
  // বাম পার্টিশন সোর্ট
  if (left < index - 1) {
    quickSort(arr, left, index - 1);
  }
  
  // ডান পার্টিশন সোর্ট
  if (index < right) {
    quickSort(arr, index, right);
  }
  
  return arr;
};

const partition = (arr, left, right) => {
  // মাঝপথি পিভট (বेहতর পারফরম্যান্স)
  const pivotIndex = Math.floor((left + right) / 2);
  const pivot = arr[pivotIndex];
  
  let i = left;
  let j = right;
  
  while (i <= j) {
    // বাম পয়েন্টার ডানে সরান
    while (arr[i] < pivot) i++;
    
    // ডান পয়েন্টার বামে সরান
    while (arr[j] > pivot) j--;
    
    // সিম্পল যদি দরকার হয়
    if (i <= j) {
      [arr[i], arr[j]] = [arr[j], arr[i]]; // ES6 সিম্পল
      i++;
      j--;
    }
  }
  
  return i; // নতুন পার্টিশন পয়েন্ট
};

// টেস্ট
const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
console.log(quickSort([...arr])); // কপি ব্যবহার করে অরিজিনাল বাঁচান
// [2, 3, 4, 6, 23, 23, 34, 34, 43, 54, 54, 232, 3434]

জটিলতা বিশ্লেষণ

পিভট সিলেকশন কৌশল

• মাঝপথি: সাধারণত ভালো পারফরম্যান্স
• মিডিয়ান-অফ-থ্রি: প্রথম, মাঝপথি, শেষের মিডিয়ান
• র‍্যান্ডম: ওয়ার্স্ট কেস এড়াতে

উৎপাদন

[ 2, 3, 4, 6, 23, 23, 34, 34, 43, 54, 54, 232, 3434 ]