Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में इंसर्शन सॉर्ट लिस्ट


मान लीजिए हमारे पास एक लिंक्ड लिस्ट है, हमें इस लिस्ट पर इंसर्शन सॉर्ट करना है। उदाहरण के लिए, यदि लिस्ट [9,45,23,71,80,55] जैसी है, तो सॉर्ट की गई लिस्ट [9,23,45,55,71,80] होगी।

हल करने के चरण

  • dummy := कुछ रैंडम मान के साथ नया नोड
  • node := दी गई लिस्ट
  • जब तक node null नहीं है
    • newNode = node का next, dummyHead := dummy का next, prevDummyHead := dummy
    • जब तक true
      • यदि dummyHead मौजूद नहीं है, या dummyHead का मान > node का मान
        • node का next := dummyHead
        • prevDummyHead का next := node
        • लूप तोड़ें
      • prevDummyHead := dummyHead, और dummyHead = dummyHead का next
    • node := nextNode
  • dummy का next वापस करें

उदाहरण

#include <bits/stdc++.h> using namespace std; class ListNode{    public:       int val;       ListNode *next;       ListNode(int data){          val = data;          next = NULL;       } }; ListNode *make_list(vector<int> v){    ListNode *head = new ListNode(v[0]);    for(int i = 1; i<v.size(); i++){       ListNode *ptr = head;       while(ptr->next != NULL){          ptr = ptr->next;       }       ptr->next = new ListNode(v[i]);    }    return head; } void print_list(ListNode *head){    ListNode *ptr = head;    cout << "[";    while(ptr){       cout << ptr->val << ", ";       ptr = ptr->next;    }    cout << "]" << endl; } class Solution {    public:    ListNode* insertionSortList(ListNode* a) {       ListNode* dummy = new ListNode(-1);       ListNode* node = a;       ListNode* nextNode;       ListNode* dummyHead;       ListNode* prevDummyHead;       while(node != NULL){          nextNode = node->next;          dummyHead = dummy->next;          prevDummyHead = dummy;          while(1){             if(!dummyHead || dummyHead->val > node->val){                node->next = dummyHead;                prevDummyHead->next = node;                break;             }             prevDummyHead = dummyHead;             dummyHead = dummyHead->next;          }          node = nextNode;       }       return dummy->next;    } }; main(){    vector<int> v = {5,3,2,0,-4,7};    ListNode *head = make_list(v);    Solution ob;    print_list(ob.insertionSortList(head)); }

इनपुट

{5,3,2,0,-4,7}

आउटपुट

[-4, 0, 2, 3, 5, 7, ]
  1. - C++ में पुनरावर्ती सम्मिलन और ट्रैवर्सल लिंक्ड सूची

    हमें पूर्णांक मान दिए गए हैं जिनका उपयोग लिंक्ड सूची बनाने के लिए किया जाएगा। कार्य है पहले एकल लिंक्ड सूची में नोड्स सम्मिलित करना और फिर पुनरावर्ती दृष्टिकोण का उपयोग करके इसे ट्रैवर्स करना। पुनरावर्ती रूप से अंत में नोड्स जोड़ना यदि head NULL है → head पर नोड जोड़ें। next पर जोड़ें। पुनरावर्ती

  1. - C++ प्रोग्राम पुनरावर्ती सम्मिलन क्रम (Recursive Insertion Sort)

    सम्मिलन क्रम (Insertion Sort) डेटा को क्रमबद्ध करने के लिए उपयोग किए जाने वाले क्रमबद्ध एल्गोरिदम में से एक है जो तत्वों को ताश के पत्तों की तरह सम्मिलित करके क्रमबद्ध करता है। सभी तत्वों को बाएं से दाएं व्यवस्थित किया जाता है फिर पहले को पहले से क्रमबद्ध मानकर, बाकी को बाईं ओर क्रमबद्ध सूची में सम्

  1. C++ में रैंडम पॉइंटर के साथ लिस्ट कॉपी करें C++ में रैंडम पॉइंटर के साथ लिस्ट कॉपी करें

    लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरा ब्लॉक अगले फील्ड का पता रखता है। मान लीजिए हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में एक रैंडम पॉइंटर होता है जो लिस्ट में अन्य नोड्स की ओर इंगित करता है।