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

C++ में स्ट्रैंड सॉर्ट

इस सेक्शन में हम देखेंगे कि C++ के स्टैंडर्ड लाइब्रेरी का उपयोग करके किसी ऐरे या लिंक्ड लिस्ट को कैसे सॉर्ट कर सकते हैं। C++ में विभिन्न उद्देश्यों के लिए कई अलग-अलग लाइब्रेरीज हैं। सॉर्टिंग उनमें से एक है।

C++ फ़ंक्शन std::list::sort() लिस्ट के एलिमेंट्स को आरोही क्रम में सॉर्ट करता है। समान एलिमेंट्स का क्रम संरक्षित रहता है। यह तुलना के लिए operator< का उपयोग करता है।

उदाहरण

#include <iostream>
#include <list>
using namespace std;

int main() {
    list<int> l = {1, 4, 2, 5, 3};
    cout << "सॉर्ट ऑपरेशन से पहले लिस्ट की सामग्री" << endl;
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;
    
    l.sort();
    
    cout << "सॉर्ट ऑपरेशन के बाद लिस्ट की सामग्री" << endl;
    for (auto it = l.begin(); it != l.end(); ++it)
        cout << *it << endl;
    return 0;
}

आउटपुट

सॉर्ट ऑपरेशन से पहले लिस्ट की सामग्री
1
4
2
5
3
सॉर्ट ऑपरेशन के बाद लिस्ट की सामग्री
1
2
3
4
5

स्ट्रैंड सॉर्ट क्या है?

मूल आर्टिकल का शीर्षक "Strand Sort" है लेकिन कोड std::list::sort() का उपयोग करता है जो आमतौर पर मर्ज सॉर्ट होता है (लिंक्ड लिस्ट के लिए उपयुक्त)। वास्तविक स्ट्रैंड सॉर्ट एक अलग एल्गोरिदम है।

वास्तविक स्ट्रैंड सॉर्ट एल्गोरिदम

#include <iostream>
#include <list>
#include <algorithm>
using namespace std;

list strandSort(list input) {
    list result;
    
    while (!input.empty()) {
        // सबलिस्ट बनाएं
        list sublist;
        sublist.push_back(input.front());
        input.pop_front();
        
        for (auto it = input.begin(); it != input.end(); ) {
            if (*it > sublist.back()) {
                sublist.push_back(*it);
                it = input.erase(it);
            } else {
                ++it;
            }
        }
        
        // मर्ज sublist को result में
        result.merge(sublist); // std::list::merge के लिए दोनों सॉर्टेड होने चाहिए
    }
    return result;
}

int main() {
    list l = {1, 4, 2, 5, 3};
    cout << "पहले: ";
    for (int x : l) cout << x << " ";
    
    l = strandSort(l);
    
    cout << "\nबाद में: ";
    for (int x : l) cout << x << " ";
    return 0;
}

आउटपुट

पहले: 1 4 2 5 3
बाद में: 1 2 3 4 5

C++ में सॉर्टिंग विकल्प

कंटेनर/मेथड एल्गोरिदम जटिलता स्थिर
std::sort (रैंडम एक्सेस) इंट्रोसॉर्ट (क्विकसॉर्ट + हीपसॉर्ट) O(n log n) नहीं
std::stable_sort मर्ज सॉर्ट O(n log n) हां
std::list::sort मर्ज सॉर्ट O(n log n) हां
std::partial_sort हीप-आधारित O(n log k) नहीं

कस्टम कम्पेरेटर

// डिसेंडिंग ऑर्डर
l.sort([](int a, int b) { return a > b; });

// स्ट्रक्चर के लिए
struct Person { string name; int age; };
list people;
people.sort([](const Person& a, const Person& b) { return a.age < b.age; });
  1. - C++ में लिंक्ड लिस्ट घुमाना (Rotate List)

    मान लीजिए हमारे पास एक लिंक्ड लिस्ट है। हमें लिस्ट को दाएं k स्थानों पर घुमाना है। k का मान ऋणात्मक नहीं है। यदि लिस्ट [1,2,3,4,5,NULL] है, और k = 2, तो आउटपुट [4,5,1,2,3,NULL] होगा। आइए चरण देखें: यदि लिस्ट खाली है, तो null वापस करें len := 1 tail := head नामक एक नोड बनाएं जब तक tail का next null

  1. - C++ में लिस्ट विभाजन (Partition List)

    मान लीजिए हमारे पास एक लिंक्ड लिस्ट और एक मान x है। हमें विभाजन करना है। विभाजन इस तरह कि x से कम सभी नोड्स उन नोड्स से पहले आएं जो x से बड़े या बराबर हैं। हमें इन दो विभाजनों में से प्रत्येक में नोड्स के मूल सापेक्ष क्रम को संरक्षित रखना चाहिए। यदि लिस्ट [1,4,3,2,5,2] है और x = 3, तो आउटपुट [1,2,2

  1. - पायथन में sort() मेथड

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