insertion sort c with examples
क्लासिक उदाहरणों के साथ सम्मिलन में एक गहराई देखो।
सम्मिलन सॉर्ट एक सॉर्टिंग तकनीक है जिसे एक तरह से देखा जा सकता है जिसे हम हाथ से खेलते हैं। जिस तरह से हम किसी कार्ड को डेक में डालते हैं या उसे निकालते हैं, उसी तरह से सम्मिलन प्रकार काम करता है।
प्रविष्टि सॉर्ट एल्गोरिथ्म तकनीक बबल सॉर्ट और चयन सॉर्ट तकनीकों की तुलना में अधिक कुशल है, लेकिन क्विकसॉर्ट और मर्ज सॉर्ट जैसी अन्य तकनीकों की तुलना में कम कुशल है।
=> यहां सर्वश्रेष्ठ C ++ प्रशिक्षण ट्यूटोरियल देखें।
आप क्या सीखेंगे:
- अवलोकन
- सामान्य एल्गोरिथम
- स्यूडोकोड
- चित्रण
- C ++ उदाहरण
- जावा उदाहरण
- प्रविष्टि सॉर्ट एल्गोरिथ्म की जटिलता विश्लेषण
- निष्कर्ष
- अनुशंसित पाठ
अवलोकन
सम्मिलन सॉर्ट तकनीक में, हम दूसरे तत्व से शुरू करते हैं और इसकी तुलना पहले तत्व से करते हैं और इसे उचित स्थान पर रखते हैं। फिर हम बाद के तत्वों के लिए यह प्रक्रिया करते हैं।
हम प्रत्येक तत्व की तुलना उसके सभी पिछले तत्वों से करते हैं और उस तत्व को उसकी उचित स्थिति में रखते या डालते हैं। तत्वों की एक छोटी संख्या के साथ सरणियों के लिए सम्मिलन सॉर्ट तकनीक अधिक संभव है। यह लिंक्ड लिस्ट को सॉर्ट करने के लिए भी उपयोगी है।
क्या xml फ़ाइलों को खोलने के लिए
लिंक की गई सूचियों में अगले तत्व (एक एकल लिंक की गई सूची के मामले में) और पिछले तत्व के लिए एक संकेतक (साथ ही एक दोहरी लिंक की गई सूची के मामले में) का एक संकेतक है। इसलिए लिंक की गई सूची के लिए प्रविष्टि सॉर्ट को लागू करना आसान हो जाता है।
आइए इस ट्यूटोरियल में इंसर्शन सॉर्ट के बारे में जानें।
सामान्य एल्गोरिथम
चरण 1 : K = 1 से N-1 के लिए चरण 2 से 5 दोहराएँ
चरण 2 : सेट टेम्प = ए (के)
चरण 3 : सेट J = K - 1
चरण 4 : अस्थायी होने पर दोहराएं<=A(J)
A (J + 1) = A (J) सेट करें
सेट जे = जे - 1
(आंतरिक लूप का अंत)
चरण 5 : A (J + 1) = अस्थायी सेट करें
(लूप का अंत)
चरण 6 : बाहर जाएं
इस प्रकार, सम्मिलन सॉर्ट तकनीक में, हम दूसरे तत्व से शुरू करते हैं क्योंकि हम मानते हैं कि पहला तत्व हमेशा सॉर्ट किया जाता है। फिर दूसरे तत्व से अंतिम तत्व तक, हम प्रत्येक तत्व की उसके पिछले तत्वों से तुलना करते हैं और उस तत्व को उचित स्थिति में रखते हैं।
स्यूडोकोड
प्रविष्टि प्रकार के लिए छद्म कोड नीचे दिया गया है।
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element whilefreePosition> 0 and array(freePosition -1) >insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedureऊपर दिए गए प्रविष्टि सॉर्ट के लिए छद्म कोड है, अगला, हम निम्नलिखित उदाहरण में इस तकनीक का वर्णन करेंगे।
चित्रण
क्रमबद्ध किए जाने वाले सारणी इस प्रकार है:
अब प्रत्येक पास के लिए, हम वर्तमान तत्व की तुलना उसके सभी पिछले तत्वों से करते हैं। तो पहले पास में, हम दूसरे तत्व से शुरू करते हैं।
इस प्रकार हमें एन संख्या पास करने की आवश्यकता होती है ताकि एन सरणी को तत्वों की पूरी तरह से छाँट सकें।
उपरोक्त दृष्टांत को सारणीबद्ध रूप में संक्षेपित किया जा सकता है:
| उत्तीर्ण करना | अनारक्षित सूची | तुलना | क्रमबद्ध सूची |
|---|---|---|---|
| 1 | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| दो | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| ३ | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| ४ | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| ५ | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| ६ | {} | {} | {1,3,5,8,10,12} |
जैसा कि ऊपर चित्रण में दिखाया गया है, हम 2 से शुरू करते हैंएन डीतत्व जैसा कि हम मानते हैं कि पहला तत्व हमेशा सॉर्ट किया जाता है। इसलिए हम दूसरे तत्व की तुलना पहले से करते हैं और यदि दूसरा तत्व पहले से कम है तो स्थिति को स्वैप कर सकते हैं।
यह तुलना और अदला-बदली प्रक्रिया दो तत्वों को उनके उचित स्थानों पर रखती है। अगला, हम तीसरे तत्व की उसके पिछले (पहले और दूसरे) तत्वों से तुलना करते हैं और तीसरे तत्व को उचित स्थान पर रखने के लिए एक ही प्रक्रिया करते हैं।
इस तरीके से, प्रत्येक पास के लिए, हम एक तत्व को उसके स्थान पर रखते हैं। पहले पास के लिए, हम इसके स्थान पर दूसरा तत्व रखते हैं। इस प्रकार, सामान्य रूप से, एन तत्वों को उनके उचित स्थान पर रखने के लिए, हमें एन -1 पास की आवश्यकता होती है।
अगला, हम C ++ भाषा में सम्मिलन सॉर्ट तकनीक के कार्यान्वयन को प्रदर्शित करेंगे।
C ++ उदाहरण
#include using namespace std; int main () { int myarray(10) = { 12,4,3,1,15,45,33,21,10,2}; cout<<'
Input list is
'; for(int i=0;i<10;i++) { cout < आउटपुट:
इनपुट सूची है
12 4 3 1 15 45 33 21 10 2
क्रमबद्ध सूची है
1 2 3 4 10 12 15 21 33 45
जावा j2ee साक्षात्कार और अनुभवी के लिए जवाब
अगला, हम सम्मिलन सॉर्ट तकनीक का जावा कार्यान्वयन देखेंगे।
जावा उदाहरण
public class Main { public static void main(String() args) { int() myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } for(int k=1; k=0 && temp <= myarray(j)) { myarray(j+1) = myarray(j); j = j-1; } myarray(j+1) = temp; } System.out.println('
sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray(i) + ' '); } } } आउटपुट:
व्यापार विश्लेषक साक्षात्कार प्रश्न और उत्तर
तत्वों की इनपुट सूची…
12 4 3 1 15 45 33 21 10 2
तत्वों की सूची…
1 2 3 4 10 12 15 21 33 45
दोनों कार्यान्वयन में, हम देख सकते हैं कि हम 2 से छंटनी शुरू करते हैंएन डीसरणी का तत्व (लूप वैरिएबल j = 1) और बार-बार वर्तमान तत्व की तुलना उसके सभी पिछले तत्वों से करता है और फिर तत्व को उसकी सही स्थिति में रखने के लिए क्रमबद्ध करता है यदि वर्तमान तत्व उसके सभी पिछले तत्वों के साथ क्रम में नहीं है।
सम्मिलन सॉर्ट सबसे अच्छा काम करता है और कुछ अंशों में पूरा किया जा सकता है यदि सरणी आंशिक रूप से सॉर्ट की जाती है। लेकिन जैसे-जैसे सूची बड़ी होती जाती है, इसका प्रदर्शन कम होता जाता है। सम्मिलन प्रकार का एक और लाभ यह है कि यह एक स्थिर प्रकार है जिसका अर्थ है कि यह सूची में समान तत्वों के क्रम को बनाए रखता है।
प्रविष्टि सॉर्ट एल्गोरिथ्म की जटिलता विश्लेषण
बबल सॉर्ट या चयन सॉर्ट की तुलना में छद्म कोड और ऊपर के चित्रण से, सम्मिलन सॉर्ट कुशल एल्गोरिथम है। लूप और वर्तमान स्थितियों के लिए उपयोग करने के बजाय, यह थोड़ी देर के लूप का उपयोग करता है जो सरणी को सॉर्ट किए जाने पर कोई अतिरिक्त चरण नहीं करता है।
हालाँकि, भले ही हम सॉर्ट किए गए एरे को इंसर्शन सॉर्ट तकनीक में पास करते हैं, फिर भी यह लूप के लिए बाहरी को निष्पादित करेगा, जिससे पहले से ही सॉर्ट किए गए एरे को सॉर्ट करने के लिए कई चरणों की आवश्यकता होगी। यह सम्मिलन का सबसे अच्छा समय जटिलता बनाता है एन का एक रैखिक कार्य करता है जहां एन सरणी में तत्वों की संख्या है।
इस प्रकार प्रविष्टि सॉर्ट तकनीक के लिए विभिन्न जटिलताएं नीचे दी गई हैं:
सबसे खराब स्थिति समय जटिलता ओ (एन 2) सबसे अच्छा मामला समय जटिलता पर) औसत समय जटिलता ओ (एन 2) अंतरिक्ष की जटिलता ओ (1)
इन जटिलताओं के बावजूद, हम अभी भी निष्कर्ष निकाल सकते हैं कि जब अन्य सॉर्टिंग तकनीक जैसे बबल सॉर्ट और चयन सॉर्ट के साथ तुलना की जाती है, तो सम्मिलन सॉर्ट सबसे कुशल एल्गोरिदम है।
निष्कर्ष
अब तक चर्चा की गई तीनों तकनीकों में प्रविष्टि सॉर्ट सबसे अधिक कुशल है। यहां, हम मानते हैं कि पहले तत्व को क्रमबद्ध किया गया है और फिर हर तत्व की तुलना अपने पिछले सभी तत्वों से की गई है और फिर वर्तमान तत्व को सरणी में अपनी सही स्थिति में रखें।
इस ट्यूटोरियल में, सम्मिलन के प्रकार पर चर्चा करते हुए हमने देखा है कि हम तत्वों की तुलना 1 के वेतन वृद्धि का उपयोग करते हैं और यह भी कि वे सन्निहित हैं। इस सुविधा के परिणामस्वरूप सॉर्ट की गई सूची प्राप्त करने के लिए अधिक पास की आवश्यकता होती है।
हमारे आगामी ट्यूटोरियल में, हम 'शेल सॉर्ट' पर चर्चा करेंगे जो चयन प्रकार पर एक सुधार है।
शेल सॉर्ट में, हम 'वृद्धि' या 'गैप' के रूप में जाना जाने वाला एक वैरिएबल पेश करते हैं, जिसके उपयोग से हम सूची को उन गैर-सन्निहित तत्वों से विभाजित करते हैं जो 'गैप' को अलग करते हैं। प्रविष्टि सॉर्ट की तुलना में शेल सॉर्ट को कम पास की आवश्यकता होती है और यह तेज़ भी है।
हमारे भविष्य के ट्यूटोरियल में, हम दो सॉर्टिंग तकनीकों, 'क्विकसॉर्ट' और 'मर्जसॉर्ट' के बारे में जानेंगे, जो डेटा सूचियों को छांटने के लिए 'डिवाइड और विजय' रणनीति का उपयोग करते हैं।
=> यहां शुरुआती सी ++ प्रशिक्षण गाइड देखें।
अनुशंसित पाठ