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

কুইকসর্ট অ্যালগরিদম

কুইকসর্টের ধাপসমূহ:

1. পিভট নির্বাচন (পছন্দমতো প্রথম/শেষ/মাঝপথি)۔
2. পিভটের ভিত্তিতে পার্টিশন।
3. লेफট পার্টিশনে রিকার্সিভ কুইকসর্ট।
4. রাইট পার্টিশনে রিকার্সিভ কুইকসর্ট।

গড় ও বেস্ট কেস: O(n log n), ওর্স্ট কেস: O(n²)।

সমাধান

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