JavaScript Quicksort पुनरावर्ती

हमें एक जावास्क्रिप्ट फ़ंक्शन लिखना आवश्यक है जो संख्याओं की एक सरणी लेता है। सरणी को बढ़ते या घटते क्रम में क्रमबद्ध करने के लिए फ़ंक्शन को क्विकॉर्ट के एल्गोरिदम को लागू करना चाहिए।

क्विकसॉर्ट एल्गोरिथम

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 ]