जल्दी से सुलझाएं

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

क्विकॉर्ट तकनीक की जटिलता

• समय जटिलता:O(n log n) सर्वोत्तम मामले और औसत मामले के लिए, O(n^2) सबसे खराब स्थिति के लिए।
• अंतरिक्ष जटिलता:O(log n)

इनपुट और आउटपुट

इनपुट:क्रमबद्ध सूची:90 45 22 11 22 50 आउटपुट:छँटाई से पहले सरणी:90 45 22 11 22 50 छँटाई के बाद सरणी:11 22 22 45 50 90

एल्गोरिदम

विभाजन (सरणी, निचला, ऊपरी)

इनपुट: डेटा सेट सरणी, निचली सीमा और ऊपरी सीमा

आउटपुट: सही स्थिति में पिवट करें

 पिवट शुरू करें:=सरणी [निचला] प्रारंभ:=निचला और अंत:=प्रारंभ करते समय ऊपरी> पिवट डू एंड:=एंड - 1 किया गया अगर स्टार्ट 

 quickSort(सरणी, बाएं, दाएं 
 

 इनपुट - डेटा की एक सरणी, और सरणी की निचली और ऊपरी सीमा
 

 आउटपुट - क्रमबद्ध सरणी
 
शुरू करें अगर निचला <दाएं तो q =विभाजन (सरणी बाएं, दाएं) QuickSort (सरणी, बाएं, q-1) QuickSort (सरणी, q+1, दाएं) अंत
 
उदाहरण
 
#include नेमस्पेस का उपयोग करके std;void swapping(int &a, int &b) { // a और b int temp की सामग्री को स्वैप करें; अस्थायी =ए; ए =बी; बी =अस्थायी;} शून्य प्रदर्शन (int * सरणी, int आकार) {के लिए (int i =0; i <आकार; i ++) cout <<सरणी [i] <<""; cout < धुरी) {अंत--; // अंत सूचक बाईं ओर चलता है} अगर (प्रारंभ <अंत) {स्वैप (सरणी [प्रारंभ], सरणी [अंत]); // छोटे और बड़े तत्व को स्वैप करें}} सरणी [निचला] =सरणी [अंत]; सरणी [अंत] =धुरी; वापसी का अंत;} त्वरित सॉर्ट करें (int * array, int left, int right) {int q; अगर (बाएं <दाएं) {क्यू =विभाजन (सरणी, बाएं, दाएं); QuickSort (सरणी, बाएँ, q-1); // बाएं उप-सरणी को क्रमबद्ध करें QuickSort (सरणी, q + 1, दाएं); // सही उप-सरणी को क्रमबद्ध करें}}int main() {int n; cout <<"तत्वों की संख्या दर्ज करें:"; सिनेमा>> एन; इंट गिरफ्तारी [एन]; // दिए गए तत्वों की संख्या के साथ एक सरणी बनाएं cout <<"तत्व दर्ज करें:" <> arr[i]; } cout <<"छँटाई से पहले सरणी:"; प्रदर्शन (गिरफ्तारी, एन); QuickSort (गिरफ्तारी, 0, n-1); //(n-1) अंतिम अनुक्रमणिका cout के लिए <<"सॉर्टिंग के बाद सरणी:"; प्रदर्शन (गिरफ्तारी, एन);}
 
आउटपुट
 
तत्वों की संख्या दर्ज करें:6तत्व दर्ज करें:90 45 22 11 22 50छँटाई से पहले सरणी:90 45 22 11 22 50छँटाई के बाद सरणी:11 22 22 45 50 90