QuickSort एल्गोरिथम

इस ट्यूटोरियल में, आप सीखेंगे कि क्विकॉर्ट कैसे काम करता है। इसके अलावा, आपको C, C ++ पायथन और जावा में क्विकसॉर्ट के काम करने के उदाहरण मिलेंगे।

क्विकॉर्ट डिवाइड और विजयी दृष्टिकोण पर आधारित एक एल्गोरिथ्म है जिसमें सरणी को उप-विभाजित किया जाता है और इन उप-सरणियों को तत्वों को सॉर्ट करने के लिए पुनरावर्ती कहा जाता है।

QuickSort कैसे काम करता है?

1. एक धुरी तत्व को सरणी से चुना जाता है। आप धुरी तत्व के रूप में सरणी से किसी भी तत्व को चुन सकते हैं।
   यहां, हमने सरणी के सबसे अंतिम (यानी अंतिम तत्व) को पिवट तत्व के रूप में लिया है। एक धुरी तत्व का चयन करें
2. धुरी तत्व से छोटे तत्वों को बाईं ओर रखा जाता है और धुरी के तत्व से अधिक तत्वों को दाईं ओर रखा जाता है। सभी छोटे तत्वों को बाईं ओर और अधिक से अधिक धुरी तत्व के दाईं ओर रखें
   उपरोक्त व्यवस्था निम्न चरणों द्वारा प्राप्त की गई है।
   1. एक सूचक धुरी तत्व पर तय किया गया है। धुरी तत्व की तुलना पहले सूचकांक से शुरू होने वाले तत्वों से की जाती है। यदि पिवट तत्व से अधिक तत्व तक पहुँच जाता है, तो उस तत्व के लिए एक दूसरा पॉइंटर सेट किया जाता है।
   2. अब, अन्य तत्वों (एक तीसरा सूचक) के साथ धुरी तत्व की तुलना की जाती है। यदि पिवट तत्व से छोटा कोई तत्व पहुँच जाता है, तो पहले पाए गए अधिक से अधिक तत्व के साथ छोटे तत्व की अदला-बदली की जाती है। अन्य तत्वों के साथ धुरी तत्व की तुलना
   3. प्रक्रिया अंतिम अंतिम तत्व तक पहुंचने तक चलती है।
      अंत में, पिवट तत्व को दूसरे पॉइंटर के साथ स्वैप किया जाता है। दूसरे पॉइंटर के साथ पिवट एलिमेंट को स्वैप करें
   4. अब इस धुरी तत्व के बाएं और दाएं हिस्से को नीचे के चरणों में आगे की प्रक्रिया के लिए लिया जाता है।
3. धुरी तत्वों को फिर से बाईं और दाईं उप-भागों के लिए अलग से चुना जाता है। इन उप-भागों के भीतर, धुरी तत्वों को उनके सही स्थान पर रखा गया है। फिर, चरण 2 दोहराया जाता है। प्रत्येक आधे में धुरी तत्व का चयन करें और पुनरावृत्ति का उपयोग करके सही जगह पर रखें
4. उप-भागों को फिर से छोटे उप-भागों में विभाजित किया जाता है जब तक कि प्रत्येक उप-भाग एक तत्व से नहीं बनता है।
5. इस बिंदु पर, सरणी पहले से ही क्रमबद्ध है।

Quicksort उप-भागों को सॉर्ट करने के लिए पुनरावर्तन का उपयोग करता है।

डिवाइड और विजेता दृष्टिकोण के आधार पर, क्विकसॉर्ट एल्गोरिथ्म के रूप में समझाया जा सकता है:

• विभाजन
  को विभाजित करने वाले बिंदु के रूप में धुरी को लेते हुए विभाजित किया जाता है। धुरी से छोटे तत्वों को धुरी के बाईं ओर रखा जाता है और धुरी से बड़े तत्वों को दाईं ओर रखा जाता है।
• जीतना
  बाएं और दाएं हिस्से में फिर से उनके लिए धुरी तत्वों का चयन करके विभाजन किया जाता है। इसे आवर्तक रूप से एल्गोरिथम में पारित करके प्राप्त किया जा सकता है।
• कम्बाइन
  यह कदम quicksort में एक महत्वपूर्ण भूमिका निभा नहीं है। सरणी पहले से ही विजेता कदम के अंत में सॉर्ट की गई है।

आप नीचे दिए गए चित्रों की सहायता से क्विकॉर्ट के काम को समझ सकते हैं।

पुनरावर्तन का उपयोग करके धुरी के बाईं ओर तत्वों को छाँटना और पुनरावृत्ति का उपयोग करके धुरी के दाईं ओर तत्वों को क्रमबद्ध करना

त्वरित क्रमबद्ध एल्गोरिथ्म

 quickSort (ऐरे, लेफ्टएंडएंडएक्स, राइटएस्टइंडेक्स) अगर (लेफ्टएस्टइंडेक्स <राइटएंडएंडएक्स) पिवेटइंडेक्स <- विभाजन (सरणी, बाएंडाइंडसेक्स, राइटएंडएंडएक्स) क्विकॉर्ट (सरणी, लेवेस्टइंडेक्स, पिवंडिंडेक्स) क्विकसॉर्ट (सरणी, पैंटीइंडैक्स 1+) ) pASTIndex storeIndex के रूप में राइटएस्टइंडेक्स सेट करें - i - leftmostIndex - 1 के लिए i <- leftmostIndex + 1 से राइटएस्टइंडेक्स यदि तत्व (i) <pivotElement स्वैप एलिमेंट (i) और एलीमेंट (storeIndex) storeIndex ++ स्वैप pivotElement और एलिमेंट (storeIndex + 1) 1 है

पायथन, जावा और सी / सी ++ उदाहरण

पायथन जावा सी सी +

 # Quick sort in Python # Function to partition the array on the basis of pivot element def partition(array, low, high): # Select the pivot element pivot = array(high) i = low - 1 # Put the elements smaller than pivot on the left and greater #than pivot on the right of pivot for j in range(low, high): if array(j) <= pivot: i = i + 1 (array(i), array(j)) = (array(j), array(i)) (array(i + 1), array(high)) = (array(high), array(i + 1)) return i + 1 def quickSort(array, low, high): if low < high: # Select pivot position and put all the elements smaller # than pivot on left and greater than pivot on right pi = partition(array, low, high) # Sort the elements on the left of pivot quickSort(array, low, pi - 1) # Sort the elements on the right of pivot quickSort(array, pi + 1, high) data = (8, 7, 2, 1, 0, 9, 6) size = len(data) quickSort(data, 0, size - 1) print('Sorted Array in Ascending Order:') print(data)

 // Quick sort in Java import java.util.Arrays; class QuickSort ( // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left and // greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; int temp = array(i); array(i) = array(j); array(j) = temp; ) ) int temp = array(i + 1); array(i + 1) = array(high); array(high) = temp; return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code public static void main(String args()) ( int() data = ( 8, 7, 2, 1, 0, 9, 6 ); int size = data.length; QuickSort qs = new QuickSort(); qs.quickSort(data, 0, size - 1); System.out.println("Sorted Array in Ascending Order: "); System.out.println(Arrays.toString(data)); ) )

 // Quick sort in C #include // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Function to print eklements of an array void printArray(int array(), int size) ( for (int i = 0; i < size; ++i) ( printf("%d ", array(i)); ) printf(""); ) // Driver code int main() ( int data() = (8, 7, 2, 1, 0, 9, 6); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); printf("Sorted array in ascending order: "); printArray(data, n); )

 // Quick sort in C++ #include using namespace std; // Function to swap position of elements void swap(int *a, int *b) ( int t = *a; *a = *b; *b = t; ) // Function to print eklements of an array void printArray(int array(), int size) ( int i; for (i = 0; i < size; i++) cout << array(i) << " "; cout << endl; ) // Function to partition the array on the basis of pivot element int partition(int array(), int low, int high) ( // Select the pivot element int pivot = array(high); int i = (low - 1); // Put the elements smaller than pivot on the left // and greater than pivot on the right of pivot for (int j = low; j < high; j++) ( if (array(j) <= pivot) ( i++; swap(&array(i), &array(j)); ) ) printArray(array, 7); cout << "… "; swap(&array(i + 1), &array(high)); return (i + 1); ) void quickSort(int array(), int low, int high) ( if (low < high) ( // Select pivot position and put all the elements smaller // than pivot on left and greater than pivot on right int pi = partition(array, low, high); // Sort the elements on the left of pivot quickSort(array, low, pi - 1); // Sort the elements on the right of pivot quickSort(array, pi + 1, high); ) ) // Driver code int main() ( int data() = (8, 7, 6, 1, 0, 9, 2); int n = sizeof(data) / sizeof(data(0)); quickSort(data, 0, n - 1); cout << "Sorted array in ascending order: "; printArray(data, n); )

क्विकॉर्ट कॉम्प्लेक्सिटी

समय की जटिलताएँ

• Worst Case Complexity (Big-O): O(n2)
  It occurs when the pivot element picked is either the greatest or the smallest element.
  This condition leads to the case in which the pivot element lies in an extreme end of the sorted array. One sub-array is always empty and another sub-array contains n - 1 elements. Thus, quicksort is called only on this sub-array.
  However, the quick sort algorithm has better performance for scattered pivots.

• Best Case Complexity (Big-omega): O(n*log n)
  It occurs when the pivot element is always the middle element or near to the middle element.
• Average Case Complexity (Big-theta): O(n*log n)
  It occurs when the above conditions do not occur.

Space Complexity

The space complexity for quicksort is O(log n).

Quicksort अनुप्रयोग

क्विकॉर्ट जब लागू किया जाता है

• प्रोग्रामिंग भाषा पुनरावृत्ति के लिए अच्छा है
• समय जटिलता मायने रखती है
• अंतरिक्ष जटिलता मायने रखती है