কুইক সোর্ট বাস্তবায়ন - JavaScript

দ্রুত এবং কার্যকর সোর্টিং অ্যালগরিদম কুইক সোর্ট বাস্তবায়ন।

অ্যালগরিদম

1. পিভট বেছে নিন
2. পার্টিশন: ছোট বামে, বড় ডানে
3. রিকার্সিভলি সাব-অ্যারে সোর্ট করুন

বাস্তবায়ন

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 pivot = arr[Math.floor((left + right) / 2)];
  let i = left, 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]];
      i++; j--;
    }
  }
  return i;
};

// Immutable ভার্সন (অরিজিনাল বদলায় না)
const quickSortImmutable = (arr) => {
  if (arr.length <= 1) return arr;
  
  const pivot = arr[Math.floor(arr.length / 2)];
  const left = arr.filter(x => x < pivot);
  const middle = arr.filter(x => x === pivot);
  const right = arr.filter(x => x > pivot);
  
  return [...quickSortImmutable(left), ...middle, ...quickSortImmutable(right)];
};

// টেস্ট
const arr = [43, 3, 34, 34, 23, 232, 3434, 4, 23, 2, 54, 6, 54];
console.log(quickSort([...arr]));           // In-place (কপি পাস)
console.log(quickSortImmutable(arr));       // Immutable
// [2, 3, 4, 6, 23, 23, 34, 34, 43, 54, 54, 232, 3434]

জটিলতা

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

• মাঝপথি (মিডিয়ান-অফ-থ্রি) - সাধারণত ভালো
• র‍্যান্ডম - ওয়ার্স্ট কেস এড়াতে
• মিডিয়ান-অফ-মিডিয়ানস - গ্যারান্টিড O(n log n)

উৎপাদন

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