---

उत्तर:

सबसे कुशल सॉर्टिंग एल्गोरिदम क्विकसॉर्ट है और ज्यादातर इस्तेमाल की जाने वाली सॉर्टिंग तकनीक भी है

यह डिवाइड एंड कॉनकॉर एक प्रकार की एल्गोरिथम है। विवरण इस प्रकार हैं:

डिवाइड

एलिमेंट और स्पलिट-ऐरे को दो सब-ऐरे में पुनर्व्यवस्थित करें और खोज के बीच में एक एलिमेंट है कि बाएं सब-ऐरे में प्रत्येक एलिमेंट औसत एलिमेंट से कम या बराबर है और दाएं सब-ऐरे में प्रत्येक एलिमेंट मध्य से बड़ा है।

कॉनकॉर

पुनरावर्ती रूप से, दो सब-ऐरे को क्रमबद्ध करें।

कंबाइन

पहले से सॉर्टेड ऐरे को मिलाएं।

QUICKSORT (array A, int a, int b)   
 1 if (b > a)   
 2 then   
 3 i ← a random index from [a,b]   
 4 swap A [i] with A[a]   
 5 o ← PARTITION (A, a, b)   
 6 QUICKSORT (A, a, o - 1)  
 7 QUICKSORT (A, o + 1, b)  

PARTITION (array A, int a, int b)   
 1 x ← A[a]   
 2 o ← a   
 3 for p ← a + 1 to b  
 4 do if (A[p] < x)   
 5 then o ← o + 1   
 6 swap A[o] with A[p]  
 7 swap A[a] with A[o]   
 8 return o 

Explaination

The first thing to do is to select a pivot number, this number will separate the data, on its left are the numbers smaller than it and the greater numbers on the right.

With this, we got the whole sequence partitioned.

After partitioning the data, we can assure that the partitions are oriented, we know that we have bigger values on the right and smaller values on the left. The quicksort uses this divide and conquer algorithm with recursion.

Therefore, now that we have the data divided we use recursion to call the same method and pass the left half of the data and after the right half to keep separating and ordinating the data.

At the end of the execution, we will have the data all sorted.

Time Complexity

Best Case Complexity

The best-case occurs when the pivot element is the middle element or near to the middle element. The best-case time complexity of quicksort is O(n*logn).

Average Case Complexity

It occurs when the array elements are in jumbled order that is not properly ascending and not properly descending. The average case time complexity of quicksort is O(n*logn).

Worst Case Complexity

The worst case occurs when the pivot element is either greatest or smallest element. Suppose, if the pivot element is always the last element of the array, the worst case would occur when the given array is sorted already in ascending or descending order. The worst-case time complexity of quicksort is O(n²).

👈       👉