quicksort java algorithm
यह ट्यूटोरियल जावा में क्विकॉर्ट अल्गोरिद्म, उसके चित्र, क्विकॉर्ट इम्प्लीमेंटेशन इन कोड उदाहरणों की मदद से समझाता है:
क्विकॉर्ट सॉर्टिंग तकनीक का व्यापक रूप से सॉफ्टवेयर अनुप्रयोगों में उपयोग किया जाता है। क्विकॉर्ट मर्ज की तरह एक विभाजित और जीत की रणनीति का उपयोग करता है।
क्विकर एल्गोरिथम में, 'पिवट' नामक एक विशेष तत्व को पहले चुना गया है और विचाराधीन सूची या सूची को दो सबसेट में विभाजित किया गया है। विभाजित उपसमूह आकार में समान हो सकते हैं या नहीं भी हो सकते हैं।
=> आसान जावा प्रशिक्षण श्रृंखला के माध्यम से पढ़ें।
विभाजन ऐसे होते हैं कि धुरी तत्व से कम सभी तत्व धुरी के बाईं ओर होते हैं और धुरी से बड़े तत्व धुरी के दाईं ओर होते हैं। Quicksort दिनचर्या पुन: दो उप-सूचियों को क्रमबद्ध करता है। Quicksort कुशलता से काम करता है और बड़ी सरणियों या सूचियों के लिए भी तेज़ होता है।
आप क्या सीखेंगे:
- क्विकॉर्ट पार्टिशन जावा
- क्विकॉर्ट्स एल्गोरिथम जावा
- त्वरित सॉर्ट के लिए स्यूडोकोड
- चित्रण
- Quicksort कार्यान्वयन जावा में
- बार बार पूछे जाने वाले प्रश्न
- निष्कर्ष
- अनुशंसित पाठ
क्विकॉर्ट पार्टिशन जावा
विभाजन Quicksort तकनीक की प्रमुख प्रक्रिया है। तो विभाजन क्या है?
परिपत्र से जुड़ी सूची c ++
किसी सरणी A को देखते हुए, हम धुरी नामक एक मान x चुनते हैं जैसे कि x से पहले के सभी तत्व x से पहले के हैं, और x से अधिक के सभी तत्व x के बाद हैं।
एक धुरी मूल्य निम्नलिखित में से कोई भी हो सकता है:
- सरणी में पहला तत्व
- सरणी में अंतिम तत्व
- सरणी में मध्य तत्व
- सरणी में कोई भी यादृच्छिक तत्व
यह पिवट मान तब ऐरे को पार्टीशन करके अपनी उचित स्थिति में रखा जाता है। इस प्रकार ing विभाजन ’प्रक्रिया का उत्पादन अपने उचित स्थान पर धुरी मूल्य है और बाईं ओर धुरी से कम तत्व और दाईं ओर एक धुरी से अधिक तत्व हैं।
विभाजन प्रक्रिया के बारे में बताने वाले निम्नलिखित आरेख पर विचार करें।
उपरोक्त आरेख एक धुरी के रूप में बार-बार अंतिम तत्व का चयन करके सरणी के विभाजन की प्रक्रिया को दर्शाता है। प्रत्येक स्तर पर, ध्यान दें कि हम अपनी सही स्थिति पर धुरी रखकर सरणी को दो उप-सरणियों में विभाजित करते हैं।
अगला, हम क्विकॉर्ट तकनीक के लिए एल्गोरिथ्म और छद्म कोड सूचीबद्ध करते हैं जिसमें विभाजन दिनचर्या भी शामिल है।
क्विकॉर्ट्स एल्गोरिथम जावा
क्विकॉर्ट के लिए सामान्य एल्गोरिथ्म नीचे दिया गया है।
quicksort(Arr, low, high) begin Declare array Arr[N] to be sorted low = 1st element; high = last element; pivot if(low क्विकॉर्ट तकनीक के लिए नीचे दिया गया छद्म कोड है।
त्वरित सॉर्ट के लिए स्यूडोकोड
निम्नलिखित एक त्वरित छँटाई तकनीक के लिए छद्म कोड है। ध्यान दें कि हमने क्विकसॉर्ट और विभाजन दिनचर्या के लिए छद्म कोड प्रदान किया है।
//pseudocode for quick sort main algorithm procedure quickSort(arr[], low, high) arr = list to be sorted low – first element of the array high – last element of array begin if (low चित्रण
आइए क्विकसॉर्ट एल्गोरिथ्म का उदाहरण देखें। एक उदाहरण के रूप में निम्नलिखित सरणी लें। यहां हमने अंतिम तत्व को धुरी के रूप में चुना है।
जैसा कि दिखाया गया है, पहला तत्व कम लेबल किया गया है और अंतिम तत्व उच्च है।
जैसा कि उपर्युक्त चित्रण में स्पष्ट है, दो बिंदु उच्च और निम्न हैं, जो क्रमशः सरणी के अंतिम और पहले तत्वों को इंगित करते हैं। इन दोनों बिंदुओं को त्वरित प्रगति के रूप में स्थानांतरित किया जाता है।
जब कम पॉइंटर द्वारा इंगित किया गया तत्व धुरी तत्व से अधिक हो जाता है और उच्च पॉइंटर द्वारा इंगित किया गया तत्व पिवट तत्व से कम होता है, तो हम निम्न और उच्च पॉइंटर द्वारा इंगित किए गए तत्वों का आदान-प्रदान करते हैं, और प्रत्येक पॉइंटर 1 स्थिति से आगे बढ़ता है।
उपरोक्त चरण तब तक किए जाते हैं जब तक दोनों बिंदु एक दूसरे को सरणी में पार नहीं करते। एक बार जब वे पार करते हैं, तो धुरी तत्व को सरणी में अपनी उचित स्थिति मिलती है। इस बिंदु पर, सरणी का विभाजन किया जाता है और अब हम प्रत्येक उप-सरणी के एक त्वरित सॉर्ट एल्गोरिथ्म को पुनरावर्ती रूप से लागू करके प्रत्येक उप-सरणी को स्वतंत्र रूप से सॉर्ट कर सकते हैं।
Quicksort कार्यान्वयन जावा में
QuickSort तकनीक को पुनरावृत्ति या पुनरावृत्ति का उपयोग करके जावा में लागू किया जा सकता है। इस खंड में, हम इन दोनों तकनीकों को देखेंगे।
पुनरावर्ती क्विकॉर्ट
हम जानते हैं कि एस्कॉर्ट की ऊपर दी गई बुनियादी तकनीक सरणी को छांटने के लिए पुनरावृत्ति का उपयोग करती है। सरणी को विभाजित करने के बाद पुनरावर्ती क्विकॉर्ट में, एस्कॉर्ट को नियमित रूप से उप-सरणियों को सॉर्ट करने के लिए पुनरावर्ती कहा जाता है।
नीचे कार्यान्वयन पुनरावृत्ति का उपयोग करके क्विकॉर्ट तकनीक प्रदर्शित करता है।
import java.util.*; class QuickSort { //selects last element as pivot, pi using which array is partitioned. int partition(int intArray[], int low, int high) { int pi = intArray[high]; int i = (low-1); // smaller element index for (int j=low; j आउटपुट:
मूल सरणी: [4, -1, 6, 8, 0, 5, -3]
क्रमबद्ध सरणी: [-3, -1, 0, 4, 5, 6, 8]
Iterative क्विकॉर्ट
पुनरावृत्ति क्विकॉर्ट्स में, हम पुनरावृत्ति और सॉर्ट विभाजन का उपयोग करने के बजाय मध्यवर्ती मापदंडों को रखने के लिए सहायक स्टैक का उपयोग करते हैं।
निम्नलिखित जावा प्रोग्राम पुनरावृति क्विकॉर्ट को लागू करता है।
import java.util.*; class Main { //partitions the array around pivot=> last element static int partition(int numArray[], int low, int high) { int pivot = numArray[high]; // smaller element index int i = (low - 1); for (int j = low; j <= high - 1; j++) { // check if current element is less than or equal to pivot if (numArray[j] <= pivot) { i++; // swap the elements int temp = numArray[i]; numArray[i] = numArray[j]; numArray[j] = temp; } } // swap numArray[i+1] and numArray[high] (or pivot) int temp = numArray[i + 1]; numArray[i + 1] = numArray[high]; numArray[high] = temp; return i + 1; } //sort the array using quickSort static void quickSort(int numArray[], int low, int high) { //auxillary stack int[] intStack = new int[high - low + 1]; // top of stack initialized to -1 int top = -1; // push initial values of low and high to stack intStack[++top] = low; intStack[++top] = high; // Keep popping from stack while is not empty while (top>= 0) { // Pop h and l high = intStack[top--]; low = intStack[top--]; // Set pivot element at its correct position // in sorted array int pivot = partition(numArray, low, high); // If there are elements on left side of pivot, // then push left side to stack if (pivot - 1 > low) { intStack[++top] = low; intStack[++top] = pivot - 1; } // If there are elements on right side of pivot, // then push right side to stack if (pivot + 1 आउटपुट:
मूल सरणी: [3, 2, 6, -1, 9, 1, -6, 10, 5]
क्रमबद्ध सरणी: [- 6, -1, 1, 2, 3, 6, 9, 10, 5]
बार बार पूछे जाने वाले प्रश्न
Q # 1) क्विकसॉर्ट कैसे काम करता है?
उत्तर: Quicksort एक विभाजन का उपयोग करता है और रणनीति को जीतता है। Quicksort पहले चयनित एक धुरी तत्व के चारों ओर एक सरणी का विभाजन करता है और उप-सरणियों को उत्पन्न करता है जो पुनरावर्ती क्रमबद्ध होते हैं।
Q # 2) क्विकसॉर्ट की समय जटिलता क्या है?
उत्तर: एक औसत पर एस्कॉर्ट की समय जटिलता हे (nlogn) है। सबसे खराब स्थिति में, यह O (n ^ 2) है जो चयन प्रकार के समान है।
Q # 3) क्विकॉर्ट का उपयोग कहां किया जाता है?
उत्तर: क्विकर का उपयोग ज्यादातर पुनरावर्ती अनुप्रयोगों में किया जाता है। क्विकॉर्ट सी-लाइब्रेरी का हिस्सा है। इसके अलावा, लगभग प्रोग्रामिंग भाषाएं जो अंतर्निहित सॉर्टिंग का उपयोग करती हैं, क्विकॉर्ट को लागू करती हैं।
Q # 4) क्विकसॉर्ट का क्या फायदा है?
उत्तर:
- क्विकर एक कुशल एल्गोरिथ्म है और तत्वों की एक विशाल सूची को भी आसानी से क्रमबद्ध कर सकता है।
- यह इन-प्लेस सॉर्ट है और इसलिए इसे अतिरिक्त स्थान या मेमोरी की आवश्यकता नहीं है।
- यह व्यापक रूप से उपयोग किया जाता है और किसी भी लंबाई के डेटा सेट को सॉर्ट करने के लिए एक कुशल तरीका प्रदान करता है।
Q # 5) क्विकसॉर्ट मर्ज सॉर्ट से बेहतर क्यों है?
उत्तर: जिस के लिए क्विकॉर्ट मर्ज सॉर्ट से बेहतर है उसका मुख्य कारण यह है कि क्विकॉर्ट इन-प्लेस सॉर्टिंग विधि है और इसके लिए अतिरिक्त मेमोरी स्पेस की आवश्यकता नहीं होती है। मर्ज सॉर्ट के लिए मध्यवर्ती सॉर्टिंग के लिए अतिरिक्त मेमोरी की आवश्यकता होती है।
निष्कर्ष
क्विकर को मुख्य रूप से O (nlogn) समय में भी एक विशाल डेटा सेट करने की दक्षता के कारण सबसे अच्छा छँटाई एल्गोरिथ्म माना जाता है।
क्विकॉर्ट भी एक इन-प्लेस सॉर्ट है और इसके लिए अतिरिक्त मेमोरी स्पेस की आवश्यकता नहीं होती है। इस ट्यूटोरियल में, हमने क्विकॉर्ट के पुनरावर्ती और पुनरावृत्ति कार्यान्वयन को देखा है।
हमारे आगामी ट्यूटोरियल में, हम जावा में छँटाई के तरीकों को जारी रखेंगे।
एक सरणी जावा से तत्वों को हटाने
=> यहाँ जावा शुरुआती गाइड पर एक नज़र रखना।
अनुशंसित पाठ
- जावा में द्विआधारी खोज एल्गोरिथम - कार्यान्वयन और उदाहरण
- जावा ऐरे - जावा में ऐरे के तत्वों को कैसे प्रिंट करें?
- चयन सॉर्ट इन जावा - चयन सॉर्ट एल्गोरिथम और उदाहरण
- एरे डेटा प्रकार - इंट एरे, डबल ऐरे, ऐरे ऑफ स्ट्रिंग्स इत्यादि।
- जावा ऐरे - घोषणा, जावा में एक ऐरे को बनाएँ और आरम्भ करें
- जावा ट्यूटोरियल फॉर बिगिनर्स: 100+ हैंड्स-ऑन जावा वीडियो ट्यूटोरियल
- जावा कॉपी ऐरे: जावा में एक ऐरे को कैसे कॉपी / क्लोन करें
- जावा सरणी कोड कोड के साथ लंबाई ट्यूटोरियल