introduction sorting techniques c
C ++ में विभिन्न सॉर्टिंग तकनीकों की सूची।
सॉर्टिंग एक तकनीक है जिसे एक विशिष्ट क्रम में डेटा को व्यवस्थित करने के लिए लागू किया जाता है। छंटाई यह सुनिश्चित करने के लिए आवश्यक है कि जो डेटा हम उपयोग करते हैं वह एक विशेष क्रम में है ताकि हम डेटा के ढेर से आवश्यक जानकारी को आसानी से प्राप्त कर सकें।
यदि डेटा अनकम्पटेड और अनसोल्ड है, जब हम एक विशेष जानकारी चाहते हैं, तो हमें डेटा को पुनः प्राप्त करने के लिए हर बार एक-एक करके इसे खोजना होगा।
=> आसान सी ++ प्रशिक्षण श्रृंखला के माध्यम से पढ़ें।
इस प्रकार यह हमेशा सलाह दी जाती है कि हम अपने डेटा को एक विशिष्ट क्रम में व्यवस्थित रखें ताकि सूचना पुनर्प्राप्ति, साथ ही डेटा पर किए गए अन्य ऑपरेशन आसानी से और कुशलता से किए जा सकें।
हम रिकॉर्ड के रूप में डेटा स्टोर करते हैं। प्रत्येक रिकॉर्ड एक या एक से अधिक क्षेत्रों से बना होता है। जब प्रत्येक रिकॉर्ड में किसी विशेष क्षेत्र का विशिष्ट मूल्य होता है, तो हम इसे एक महत्वपूर्ण फ़ील्ड कहते हैं। उदाहरण के लिए, एक कक्षा में, रोल नंबर एक अनूठा या महत्वपूर्ण क्षेत्र हो सकता है।
स्पाइवेयर सेल फोन पर डाल करने के लिए
हम किसी विशेष कुंजी क्षेत्र पर डेटा को सॉर्ट कर सकते हैं और फिर इसे आरोही / बढ़ते क्रम में या अवरोही / घटते क्रम में व्यवस्थित कर सकते हैं।
इसी तरह, एक टेलीफोन डिक्शनरी में, हर रिकॉर्ड में एक व्यक्ति का नाम, पता और टेलीफोन नंबर होता है। इसमें, टेलीफोन नंबर एक विशिष्ट या महत्वपूर्ण क्षेत्र है। हम इस टेलीफोन क्षेत्र पर शब्दकोश के डेटा को सॉर्ट कर सकते हैं। वैकल्पिक रूप से, हम डेटा को संख्यात्मक या अल्फ़ान्यूमेरिक रूप से भी सॉर्ट कर सकते हैं।
जब हम डेटा को किसी अन्य सहायक मेमोरी की आवश्यकता के बिना मुख्य मेमोरी में ही सॉर्ट करने के लिए समायोजित कर सकते हैं, तो हम इसे कहते हैं आंतरिक छँटाई ।
दूसरी ओर, जब हमें छँटाई के दौरान मध्यवर्ती डेटा को संग्रहीत करने के लिए सहायक मेमोरी की आवश्यकता होती है, तो हम तकनीक को कहते हैं बाहरी छँटाई ।
इस ट्यूटोरियल में, हम C ++ में विभिन्न सॉर्टिंग तकनीकों के बारे में विस्तार से जानेंगे।
आप क्या सीखेंगे:
सी ++ में छंटनी तकनीक
C ++ नीचे दिए गए अनुसार विभिन्न छँटाई तकनीकों का समर्थन करता है।
बुलबुले की तरह
बबल सॉर्ट सबसे सरल तकनीक है, जिसमें हम हर तत्व की उसके आसन्न तत्व से तुलना करते हैं और तत्वों को स्वैप करते हैं यदि वे क्रम में नहीं हैं। इस तरह से हर पुनरावृत्ति (एक पास कहा जाता है) के अंत में, सबसे भारी तत्व सूची के अंत में बुदबुदाती है।
नीचे दिए गए बबल सॉर्ट का एक उदाहरण है।
क्रमबद्ध किया जाना है:
जैसा कि ऊपर से देखा गया है कि यह एक छोटा सा सरणी है और लगभग छँट चुका है, हम कुछ पासों में पूरी तरह से क्रमबद्ध सरणी प्राप्त करने में कामयाब रहे।
आइए हम C ++ में बबल सॉर्ट तकनीक को लागू करते हैं।
#include using namespace std; int main () { int i, j,temp; int a(5) = {10,2,0,43,12}; cout <<'Input list ...
'; for(i = 0; i<5; i++) { cout < आउटपुट:
इनपुट सूची…
१० २ ० ४३ १२
क्रमबद्ध तत्व सूची…
0 2 10 12 43
जैसा कि आउटपुट से देखा जाता है, बबल सॉर्ट तकनीक में, हर पास के साथ सबसे भारी तत्व को सरणी के अंत तक बुदबुदाया जाता है, जिससे सरणी पूरी तरह से छंटनी होती है।
चयन छांटना
तकनीक को लागू करना आसान है, जिसमें हम सूची में सबसे छोटे तत्व को ढूंढते हैं और इसे उचित स्थान पर रख देते हैं। प्रत्येक पास पर, अगले सबसे छोटे तत्व को चुना जाता है और उसे उचित स्थिति में रखा जाता है।
आइए हम पिछले उदाहरण के समान सरणी लें और इस सरणी को क्रमबद्ध करने के लिए चयन क्रमबद्ध करें।
जैसा कि ऊपर चित्रण में दिखाया गया है, एन संख्या के तत्वों के लिए हम सरणी को पूरी तरह से सॉर्ट करने के लिए एन -1 पास लेते हैं। हर पास के अंत में, सरणी में सबसे छोटा तत्व को सॉर्ट किए गए सरणी में उचित स्थान पर रखा गया है।
इसके बाद, C ++ का उपयोग करके चयन सॉर्ट को लागू करते हैं।
#include using namespace std; int findSmallest (int(),int); int main () { int myarray(5) = {12,45,8,15,33}; int pos,temp; cout<<'
Input list of elements to be Sorted
'; for(int i=0;i<5;i++) { cout< आउटपुट:
छांटे जाने वाले तत्वों की इनपुट सूची
12 45 8 15 33
तत्वों की क्रमबद्ध सूची है
१२ १५ ३३ ४५
चयन क्रम में, प्रत्येक पास के साथ, सरणी में सबसे छोटा तत्व अपनी उचित स्थिति में रखा जाता है। इसलिए छँटाई प्रक्रिया के अंत में, हमें पूरी तरह से छँटाई हुई सरणी मिलती है।
सम्मिलन सॉर्ट
सम्मिलन सॉर्ट एक तकनीक है जिसमें हम सूची के दूसरे तत्व से शुरू करते हैं। हम दूसरे तत्व की उसके पिछले (1) से तुलना करते हैंअनुसूचित जनजाति) तत्व और इसे अपने उचित स्थान पर रखें। अगले पास में, प्रत्येक तत्व के लिए, हम इसकी सभी पिछले तत्वों से तुलना करते हैं और उस तत्व को उसके उचित स्थान पर सम्मिलित करते हैं।
उपरोक्त तीन छंटाई तकनीक सरल और लागू करने में आसान है। सूची आकार छोटा होने पर ये तकनीक अच्छा प्रदर्शन करती हैं। जैसा कि सूची आकार में बढ़ती है, ये तकनीक उस कुशलता से प्रदर्शन नहीं करती हैं।
निम्नलिखित दृष्टांत को समझने से तकनीक स्पष्ट होगी।
क्रमबद्ध किए जाने वाले सरणी इस प्रकार है:
अब प्रत्येक पास के लिए, हम वर्तमान तत्व की तुलना उसके सभी पिछले तत्वों से करते हैं। इस प्रकार पहले पास में, हम दूसरे तत्व से शुरू करते हैं।
इसलिए हमें एन संख्या पास करने की आवश्यकता है ताकि एक सरणी पूरी तरह से तत्वों की संख्या को सॉर्ट कर सके।
C ++ का उपयोग करके सम्मिलन सॉर्ट तकनीक को लागू करें।
#include using namespace std; int main () { int myarray(5) = { 12,4,3,1,15}; cout<<'
Input list is
'; for(int i=0;i<5;i++) { cout < आउटपुट:
इनपुट सूची है
१२ ४ ३ १ १५
क्रमबद्ध सूची है
१ ३ ४ १२ १५
उपरोक्त आउटपुट प्रविष्टि सॉर्ट का उपयोग करके पूर्ण सॉर्ट किए गए सरणी को दिखाता है।
जल्दी से सुलझाएं
क्विकसॉर्ट सबसे कुशल एल्गोरिदम है जिसका उपयोग डेटा को सॉर्ट करने के लिए किया जा सकता है। यह तकनीक 'विभाजित और जीतना' रणनीति का उपयोग करती है जिसमें समस्या को कई उप-उपखंडों में विभाजित किया जाता है और इन उपप्रकारों को हल करने के बाद व्यक्तिगत रूप से एक पूर्ण रूप से क्रमबद्ध सूची के लिए विलय कर दिया जाता है।
क्विकॉर्ट्स में, हम पहले सूची को पिवट एलिमेंट के चारों ओर विभाजित करते हैं और फिर पिवट एलिमेंट के अनुसार अन्य तत्वों को उनके उचित पदों पर रखते हैं।
जैसा कि ऊपर चित्रण में दिखाया गया है, क्विकॉर्ट तकनीक में हम एक धुरी तत्व के चारों ओर सरणी को विभाजित करते हैं, ताकि धुरी की तुलना में कम सभी तत्व उसके बाईं ओर हों जो धुरी की तुलना में अधिक हो। फिर हम इन दो सरणियों को स्वतंत्र रूप से लेते हैं और उन्हें क्रमबद्ध करते हैं और फिर परिणामी क्रमबद्ध सरणी प्राप्त करने के लिए उन्हें जोड़ते हैं या जीतते हैं।
क्विकॉर्ट की कुंजी धुरी तत्व का चयन है। यह सरणी का पहला, अंतिम या मध्य तत्व हो सकता है। धुरी तत्व का चयन करने के बाद पहला कदम धुरी को उसकी सही स्थिति में रखना है ताकि हम सरणी को उचित रूप से विभाजित कर सकें।
आइए C ++ का उपयोग करके त्वरित सॉर्ट तकनीक को लागू करें।
#include using namespace std; // Swap two elements - Utility function void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; } // partition the array using last element as pivot int partition (int arr(), int low, int high) { int i = (low - 1); for (int j = low; j <= high- 1; j++) { //if current element is smaller than pivot, increment the low element //swap elements at i and j if (arr(j) <= pivot) { i++; // increment index of smaller element swap(&arr(i), &arr(j)); } } swap(&arr(i + 1), &arr(high)); return (i + 1); } //quicksort algorithm void quickSort(int arr(), int low, int high) { if (low < high) { //partition the array int pivot = partition(arr, low, high); //sort the sub arrays independently quickSort(arr, low, pivot - 1); quickSort(arr, pivot + 1, high); } } void displayArray(int arr(), int size) { int i; for (i=0; i < size; i++) cout< आउटपुट:
इनपुट सरणी
12 23 3 43 51
ऐरे क्वर्टोर्ट के साथ सॉर्ट किया गया
3 12 23 43 51
ऊपर दिए गए क्विकसर्ट कार्यान्वयन में, हमारे पास एक विभाजन दिनचर्या है जिसका उपयोग इनपुट तत्व को एक धुरी तत्व के चारों ओर विभाजित करने के लिए किया जाता है जो कि सरणी में अंतिम तत्व है। फिर हम क्विकॉर्ट रूटीन को पुनरावर्ती रूप से उप-सरणियों को व्यक्तिगत रूप से क्रमबद्ध करने के लिए कहते हैं जैसा चित्रण में दिखाया गया है।
मर्ज़ सॉर्ट
यह एक और तकनीक है जो 'डिवाइड और विजय' रणनीति का उपयोग करती है। इस तकनीक में, हम सूची को पहले समान हिस्सों में विभाजित करते हैं। फिर हम इन सूचियों पर स्वतंत्र रूप से मर्ज सॉर्ट तकनीक का प्रदर्शन करते हैं ताकि दोनों सूचियाँ क्रमबद्ध हों। अंत में, हम पूरी सूची वाली सूची प्राप्त करने के लिए दोनों सूचियों को मिला देते हैं।
मर्ज सॉर्ट और क्विक सॉर्ट अधिकांश अन्य सॉर्टिंग तकनीकों की तुलना में तेज़ हैं। जब सूची आकार में बड़ी हो जाती है तब भी उनका प्रदर्शन बरकरार रहता है।
आइए हम मर्ज सॉर्ट तकनीक का एक चित्रण देखें।
उपरोक्त दृष्टांत में, हम देखते हैं कि मर्ज सॉर्ट तकनीक मूल सरणी को बार-बार सबरेज़ में विभाजित करती है, जब तक कि प्रत्येक सबरे में केवल एक तत्व न हो। एक बार यह हो जाने के बाद, सबरेज़ को स्वतंत्र रूप से सॉर्ट किया जाता है और एक साथ मिलकर एक पूर्ण सॉर्ट किया गया सरणी बनता है।
अगला, आइए C ++ भाषा का उपयोग करके मर्ज सॉर्ट लागू करें।
#include using namespace std; void merge(int *,int, int , int ); void merge_sort(int *arr, int low, int high) { int mid; if (low num; cout<<'Enter '<myarray(i); } merge_sort(myarray, 0, num-1); cout<<'Sorted array
'; for (int i = 0; i < num; i++) { cout< आउटपुट:
सॉर्ट किए जाने वाले तत्वों की संख्या दर्ज करें: 5
सॉर्ट किए जाने वाले 5 तत्वों को दर्ज करें: 10 21 47 3 59
क्रमबद्ध सरणी
3 10 21 47 59
शेल सॉर्ट
शैल सॉर्ट सम्मिलन सॉर्ट तकनीक का एक विस्तार है। सम्मिलन प्रकार में, हम केवल अगले तत्व के साथ सौदा करते हैं, जबकि शेल प्रकार में, हम एक वेतन वृद्धि या एक अंतर प्रदान करते हैं, जिसके उपयोग से हम मूल सूची से छोटी सूची बनाते हैं। सब्लिस्ट में तत्वों को सन्निहित नहीं होना चाहिए, बल्कि वे आमतौर पर। Gap_value ’अलग होते हैं।
शैल सॉर्ट सम्मिलन सॉर्ट की तुलना में अधिक तेज़ी से करता है और सम्मिलन सॉर्ट की तुलना में कम चाल की आवश्यकता होती है।
यदि हम एक अंतर प्रदान करते हैं, तो हमारे पास प्रत्येक तत्व के साथ निम्नलिखित उप-सूचियाँ होंगी जो 3 तत्वों से अलग हैं।
हम फिर इन तीन उपशास्त्रियों को क्रमबद्ध करते हैं।
सॉर्ट किए गए उप-सरणियों को मर्ज करने के बाद हमने जो उपर्युक्त सरणी प्राप्त की है, वह लगभग क्रमबद्ध है। अब हम इस सरणी पर संपूर्ण सरणी को सॉर्ट करने के लिए सम्मिलन सॉर्ट कर सकते हैं।
इस प्रकार हम देखते हैं कि एक बार जब हम उचित वेतन वृद्धि का उपयोग करके सरणी को उप-विभाजकों में विभाजित करते हैं और फिर उन्हें एक साथ विलय कर देते हैं तो हमें लगभग छँटाई सूची मिलती है। इस सूची पर प्रविष्टि सॉर्ट तकनीक का प्रदर्शन किया जा सकता है और सरणी को मूल प्रविष्टि सॉर्ट की तुलना में कम चाल में सॉर्ट किया जाता है।
नीचे दिए गए C ++ में शैल सॉर्ट का कार्यान्वयन है।
#include using namespace std; // shellsort implementation int shellSort(int arr(), int N) { for (int gap = N/2; gap > 0; gap /= 2) { for (int i = gap; i = gap && arr(j - gap) > temp; j -= gap) arr(j) = arr(j - gap); arr(j) = temp; } } return 0; } int main() { int arr() = {45,23,53,43,18}; //Calculate size of array int N = sizeof(arr)/sizeof(arr(0)); cout << 'Array to be sorted:
'; for (int i=0; i आउटपुट:
क्रमबद्ध किया जाना है:
४५ २३ ५३ ४३ १ 18
शेल प्रकार के बाद सरणी:
18 23 43 45 53
शेल प्रकार इस प्रकार सम्मिलन प्रकार पर एक बड़ा सुधार के रूप में कार्य करता है और सरणी को सॉर्ट करने के लिए चरणों की आधी संख्या भी नहीं लेता है।
ढेर बनाएं और छांटें
हीप्सर्ट एक ऐसी तकनीक है जिसमें डेटा संरचना (न्यूनतम-ढेर या अधिकतम-ढेर) का उपयोग सूची को सॉर्ट करने के लिए किया जाता है। हम पहले अनसोल्ड लिस्ट से ढेर बनाते हैं और एरे को सॉर्ट करने के लिए भी हीप का इस्तेमाल करते हैं।
हीप्सोर्ट कुशल है लेकिन त्वरित या मर्ज प्रकार के रूप में नहीं।
जैसा कि ऊपर चित्रण में दिखाया गया है, हम सबसे पहले एक अधिकतम ढेर का निर्माण करते हैं जो सरणी तत्वों से छँटा जाता है। फिर हम ढेर को पार करते हैं और अंतिम और पहले तत्व को स्वैप करते हैं। इस समय अंतिम तत्व पहले से ही क्रमबद्ध है। फिर हम शेष तत्वों में से एक अधिकतम ढेर का निर्माण करते हैं।
फिर से ढेर को पीछे करें और पहले और अंतिम तत्वों को स्वैप करें और अंतिम तत्व को सॉर्ट की गई सूची में जोड़ें। यह प्रक्रिया तब तक जारी रखी जाती है जब तक कि ढेर में केवल एक तत्व न बचा हो जो क्रमबद्ध सूची का पहला तत्व बन जाता है।
आइए अब C ++ का उपयोग करते हुए हीप सॉर्ट को लागू करें।
#include using namespace std; // function to heapify the tree void heapify(int arr(), int n, int root) { int largest = root; // root is the largest element int l = 2*root + 1; // left = 2*root + 1 int r = 2*root + 2; // right = 2*root + 2 // If left child is larger than root if (l arr(largest)) largest = l; // If right child is larger than largest so far if (r arr(largest)) largest = r; // If largest is not root if (largest != root) { //swap root and largest swap(arr(root), arr(largest)); // Recursively heapify the sub-tree heapify(arr, n, largest); } } // implementing heap sort void heapSort(int arr(), int n) { // build heap for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // extracting elements from heap one by one for (int i=n-1; i>=0; i--) { // Move current root to end swap(arr(0), arr(i)); // again call max heapify on the reduced heap heapify(arr, i, 0); } } /* print contents of array - utility function */ void displayArray(int arr(), int n) { for (int i=0; i आउटपुट:
इनपुट सरणी
४ १ 4 ३ १२ ९
क्रमबद्ध सरणी
३ ४ ९ १२ १ 17
अब तक हमने एक चित्रण के साथ सभी प्रमुख छँटाई तकनीकों पर संक्षेप में चर्चा की है। हम इनमें से प्रत्येक तकनीक को प्रत्येक तकनीक को समझने के लिए विभिन्न उदाहरणों के साथ अपने बाद के ट्यूटोरियल में विस्तार से जानेंगे।
निष्कर्ष
डेटा को क्रमबद्ध और उचित क्रम में रखने के लिए छंटाई आवश्यक है। Unsorted और unkempt को पहुंचने में अधिक समय लग सकता है और इस प्रकार पूरे कार्यक्रम के प्रदर्शन पर असर पड़ सकता है। इस प्रकार डेटा से संबंधित किसी भी संचालन जैसे कि एक्सेस करना, खोजना, हेरफेर करना, आदि के लिए हमें डेटा को सॉर्ट करने की आवश्यकता होती है।
प्रोग्रामिंग में कई सॉर्टिंग तकनीक कार्यरत हैं। प्रत्येक तकनीक को उस डेटा संरचना के आधार पर नियोजित किया जा सकता है जिसका उपयोग हम एल्गोरिदम द्वारा लिए गए डेटा या मेमोरी स्पेस को डेटा सॉर्ट करने के लिए किए गए समय के आधार पर कर रहे हैं। जिस तकनीक का हम उपयोग कर रहे हैं वह इस बात पर भी निर्भर करता है कि हम किस डेटा संरचना को छाँट रहे हैं।
सॉर्टिंग तकनीक हमें एक विशिष्ट क्रम में हमारे डेटा संरचनाओं को सॉर्ट करने और तत्वों को आरोही या अवरोही क्रम में व्यवस्थित करने की अनुमति देती है। हमने बबल सॉर्ट, सेलेक्शन सॉर्ट, इंसर्शन सॉर्ट, क्विकॉर्ट, शेल सॉर्ट, मर्ज सॉर्ट और हीप सॉर्ट जैसी तकनीकों को देखा है। बबल सॉर्ट और चयन प्रकार सरल और लागू करने में आसान होते हैं।
हमारे बाद के ट्यूटोरियल में, हम ऊपर दी गई छंटाई तकनीकों में से प्रत्येक को विस्तार से देखेंगे।
=> फ्री सी ++ कोर्स के लिए यहां क्लिक करें।
अनुशंसित पाठ
- उदाहरणों के साथ C ++ में ढेर छाँटें
- उदाहरणों के साथ C ++ में मर्ज करें
- उदाहरणों के साथ C ++ में प्रविष्टि सॉर्ट करें
- JMeter वीडियो 1: परिचय, JMeter डाउनलोड और इंस्टॉल करें
- जावा प्रोग्रामिंग भाषा का परिचय - वीडियो ट्यूटोरियल
- पायथन परिचय और स्थापना प्रक्रिया
- सिंटैक्स, विकल्प और उदाहरण के साथ यूनिक्स सॉर्ट कमांड
- MongoDB सॉर्ट () उदाहरण के साथ विधि
