मेन्यू

सम्मिलन क्रमबद्ध जावा में - सम्मिलन क्रमबद्ध एल्गोरिथ्म और उदाहरण

  • मुख्य
  • अन्य
  • सम्मिलन क्रमबद्ध जावा में - सम्मिलन क्रमबद्ध एल्गोरिथ्म और उदाहरण

insertion sort java insertion sort algorithm examples

समस्याओं को खत्म करने के लिए हमारे साधन का प्रयास करें

यह ट्यूटोरियल जावा में अपने अलगोरिदम, छद्म कोड और सॉर्टिंग एरे के उदाहरण, सिंगली लिंक्ड और डाउली लिंक्ड लिस्ट सहित इंसर्ट को शामिल करता है।

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

=> यहाँ जावा शुरुआती गाइड पर एक नज़र रखना।

विंडोज़ में बिन फाइलें कैसे खोलें

सम्मिलन जावा में क्रमबद्ध करें

आप क्या सीखेंगे:

सम्मिलन का परिचय जावा में क्रमबद्ध करें

सम्मिलन सॉर्ट तकनीक में, हम मानते हैं कि सूची में पहला तत्व पहले से ही सॉर्ट किया गया है और हम दूसरे तत्व से शुरू करते हैं। दूसरे तत्व की तुलना पहले के साथ की जाती है और क्रम में न होने पर स्वैप किया जाता है। यह प्रक्रिया बाद के सभी तत्वों के लिए दोहराई जाती है।

सामान्य तौर पर, सम्मिलन सॉर्ट तकनीक प्रत्येक तत्व की उसके पिछले तत्वों से तुलना करती है और तत्व को उसकी उचित स्थिति में रखने के लिए सॉर्ट करती है।

जैसा कि पहले ही उल्लेख किया गया है, सम्मिलन सॉर्ट तकनीक डेटा के एक छोटे सेट के लिए अधिक संभव है, और इस प्रकार कम संख्या में तत्वों के साथ सरणियों को कुशलता से सम्मिलन सॉर्ट का उपयोग करके सॉर्ट किया जा सकता है।

सम्मिलन सॉर्ट विशेष रूप से लिंक किए गए सूची डेटा संरचनाओं को सॉर्ट करने में उपयोगी है। जैसा कि आप जानते हैं, लिंक की गई सूचियों में इसके अगले तत्व (एकल लिंक की गई सूची) और पिछले तत्व (डबल लिंक की गई सूची) की ओर इशारा करते हैं। इससे पिछले और अगले तत्वों पर नज़र रखना आसान हो जाता है।

इस प्रकार लिंक्ड सूचियों को छांटने के लिए सम्मिलन प्रकार का उपयोग करना आसान है। हालाँकि, डेटा आइटम अधिक होने पर सॉर्ट करने में बहुत समय लगेगा।

इस ट्यूटोरियल में, हम इसके एल्गोरिथ्म, छद्म कोड और उदाहरण सहित सम्मिलन सॉर्ट तकनीक पर चर्चा करेंगे। हम एक सरणी सॉर्ट करने के लिए जावा प्रोग्राम को भी कार्यान्वित करेंगे, एक प्रकार से लिंक की गई सूची, और प्रविष्टि सॉर्ट का उपयोग करते हुए डाउनली लिंक्ड सूची।

सम्मिलन क्रमबद्ध एल्गोरिथम

प्रविष्टि सॉर्ट एल्गोरिथ्म इस प्रकार है।

चरण 1 : K = 1 से N-1 के लिए चरण 2 से 5 दोहराएँ

चरण 2 : सेट टेम्प = ए (के)

चरण 3 : सेट J = K - 1

चरण 4 :

अस्थायी रहते हुए दोहराएं<=A(J)
A (J + 1) = A (J) सेट करें
सेट जे = जे - 1
(आंतरिक लूप का अंत)

चरण 5 :

सेट ए (जे + 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 while freePosition > 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

अगला, आइए हम एक चित्रण देखते हैं जो सम्मिलन प्रकार का उपयोग करके एक सरणी को छाँटने का प्रदर्शन करता है।

सम्मिलन का उपयोग करके एक सरणी को क्रमबद्ध करना

एक एरे का उपयोग करके इंसर्शन सॉर्ट का एक उदाहरण लेते हैं।

क्रमबद्ध किए जाने वाले सारणी इस प्रकार है:

सरणी को सॉर्ट किया जाना है

अब प्रत्येक पास के लिए, हम वर्तमान तत्व की तुलना उसके सभी पिछले तत्वों से करते हैं। तो पहले पास में, हम दूसरे तत्व से शुरू करते हैं।

2 तत्व की तुलना 1 तत्व से करें

पास २

पास ३

पास ४

पास ५

पास ६

इस प्रकार, हमें एन की संख्या की आवश्यकता होती है ताकि एन सरणी को तत्वों की पूरी तरह से छाँट सकें।

कैसे एक पीसी पर एक eps फ़ाइल खोलने के लिए

उपरोक्त चित्र को सारणीबद्ध रूप में संक्षेप में प्रस्तुत किया जा सकता है:

उत्तीर्ण करनाअनारक्षित सूचीतुलनाक्रमबद्ध सूची
1{10,2,6,15,4,1}{१०.२}{2,10, 6,15,4,1}
दो{2,10, 6,15,4,1}{2,10, 6}{2,6,10,15,4,1}
३{2,6,10,15,4,1}{2.6, 10.15}{2,6,10,15,4,1}
४{2,6,10,15,4,1}{2.6, 10.15.4}{2,4,6,10,15,1}
५{2,4,6,10,15,1}{2,4,6,10,15,1}{1,2,4,6, 10,15}
६{}{}{1,2,4,6, 10,15}

जैसा कि ऊपर चित्रण में दिखाया गया है, प्रत्येक पास के अंत में, एक तत्व अपने उचित स्थान पर जाता है। इसलिए सामान्य तौर पर, एन तत्वों को उनके उचित स्थान पर रखने के लिए, हमें एन -1 पास की आवश्यकता होती है।

सम्मिलन क्रमबद्ध कार्यान्वयन जावा में

निम्नलिखित कार्यक्रम जावा में सम्मिलन प्रकार के कार्यान्वयन को दर्शाता है। यहां, हमारे पास प्रविष्टि सॉर्ट का उपयोग करके सॉर्ट किया जाना है।

import java.util.*; public class Main { public static void main(String() args) { //declare an array and print the original contents int() numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray(j)) { numArray(j+1) = numArray(j); j = j-1; } numArray(j+1) = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } }

आउटपुट:

मूल सरणी: (१०, ६, १५, ४, १, ४५)
क्रमबद्ध सरणी: (1, 4, 6, 10, 15, 45)

प्रविष्टि सॉर्ट का कार्यान्वयन - आउटपुट

उपरोक्त कार्यान्वयन में, यह देखा जाता है कि छंटाई 2 से शुरू होती हैएन डीसरणी का तत्व (लूप वेरिएबल j = 1) और फिर वर्तमान तत्व की तुलना उसके पिछले तत्वों से की जाती है। तत्व को तब उसकी सही स्थिति में रखा जाता है।

सम्मिलन सॉर्ट प्रभावी रूप से छोटे सरणियों के लिए और उन सरणियों के लिए प्रभावी रूप से काम करता है जो आंशिक रूप से क्रमबद्ध होते हैं जहां छांटना कम पास में पूरा होता है।

सम्मिलन सॉर्ट एक स्थिर सॉर्ट है यानी यह सूची में समान तत्वों के क्रम को बनाए रखता है।

सम्मिलन का उपयोग कर एक लिंक की गई सूची को क्रमबद्ध करना

निम्न जावा प्रोग्राम सम्मिलन प्रकार का उपयोग करके एक एकल लिंक की गई सूची को सॉर्ट करना दिखाता है।

import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val

आउटपुट:

एक और फोन पर जासूसी करने के लिए एंड्रॉयड ऐप

मूल लिंक की गई सूची:
1 8 32 2 10
क्रमबद्ध लिंक्ड सूची:
१ २ 1 १० ३२

आउटपुट - लिंक की गई सूची

उपरोक्त कार्यक्रम में, हमने एक वर्ग को परिभाषित किया है जो एक लिंक की गई सूची बनाता है और इसमें नोड्स के साथ-साथ इसे सॉर्ट करता है। चूंकि एकल लिंक की गई सूची में अगला पॉइंटर है, इसलिए सूची को सॉर्ट करते समय नोड्स का ट्रैक रखना आसान होता है।

प्रविष्टि सॉर्टिंग का उपयोग करके एक संदिग्ध-लिंक्ड सूची को क्रमबद्ध करना

निम्न प्रोग्राम सम्मिलन सॉर्ट का उपयोग करके एक डबल-लिंक की गई सूची सॉर्ट करता है। ध्यान दें कि चूंकि दोगुनी लिंक की गई सूची में पिछले और अगले दोनों बिंदु हैं, इसलिए डेटा को सॉर्ट करते समय पॉइंटर्स को अपडेट और राहत देना आसान है।

class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args()) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println(' Sorted Doubly Linked List:'); print_DLL(head); } }

आउटपुट:

मूल रूप से लिंक की गई दोहरी सूची:
१ १ २ २ 7 ३ ५
क्रमबद्ध डबली लिंक्ड सूची:
1 2 3 5 7 11

आउटपुट - संदेह से जुड़ी सूची

बार बार पूछे जाने वाले प्रश्न

Q # 1) जावा में इंसर्शन सॉर्ट क्या है?

उत्तर: सम्मिलन सॉर्ट जावा में एक सरल सॉर्टिंग तकनीक है जो एक छोटे डेटा सेट और जगह के लिए कुशल है। यह माना जाता है कि पहले तत्व को हमेशा सॉर्ट किया जाता है और फिर प्रत्येक बाद वाले तत्व की तुलना उसके सभी पिछले तत्वों से की जाती है और उसे उचित स्थिति में रखा जाता है।

क्यू # 2) इंसर्शन सॉर्ट बेहतर क्यों है?

उत्तर: छोटे डेटा सेटों के लिए इंसर्शन सॉर्ट तेजी से होता है जब अन्य तकनीकें जैसे त्वरित पुनरावर्ती कॉल के माध्यम से ओवरहेड जोड़ते हैं। प्रविष्टि सॉर्टिंग अन्य छँटाई एल्गोरिदम की तुलना में अपेक्षाकृत अधिक स्थिर है और कम मेमोरी की आवश्यकता होती है। सम्मिलन सॉर्ट भी अधिक कुशलता से काम करता है जब सरणी लगभग हल हो जाती है।

क्यू # 3) प्रविष्टि सॉर्ट किसके लिए उपयोग किया जाता है?

उत्तर: सम्मिलन सॉर्ट का उपयोग ज्यादातर कंप्यूटर अनुप्रयोगों में किया जाता है जो फ़ाइल खोज, पथ-खोज और डेटा संपीड़न जैसे जटिल कार्यक्रमों का निर्माण करते हैं।

क्यू # 4)प्रविष्टि सॉर्ट की दक्षता क्या है?

उत्तर: सम्मिलन सॉर्ट में O (n ^ 2) का औसत केस प्रदर्शन होता है। सम्मिलन प्रकार के लिए सबसे अच्छा मामला तब होता है जब सरणी पहले से छंटनी होती है और यह ओ (एन) है। प्रविष्टि प्रकार के लिए सबसे खराब स्थिति वाला प्रदर्शन फिर से हे (n ^ 2) है।

निष्कर्ष

सम्मिलन सॉर्ट एक सरल सॉर्टिंग तकनीक है जो Arrays या लिंक्ड सूची पर काम करती है। डेटा सेट छोटा होने पर यह उपयोगी है। जैसे-जैसे डेटा सेट बड़ा होता जाता है, यह तकनीक धीमी और अक्षम होती जाती है।

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

प्रविष्टि सॉर्ट लिंक्ड सूची को अच्छी तरह से काम करता है जो एकल और डबल-लिंक्ड सूची दोनों हैं। ऐसा इसलिए है क्योंकि लिंक की गई सूची नोड्स से बनी है जो पॉइंटर्स के माध्यम से जुड़े हुए हैं। इसलिए नोड्स को छांटना आसान हो जाता है।

हमारे आगामी ट्यूटोरियल में, हम जावा में एक और छँटाई तकनीक पर चर्चा करेंगे।

=> आसान जावा प्रशिक्षण श्रृंखला के माध्यम से पढ़ें।

अनुशंसित पाठ

^