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

C++ में इंसर्शन सॉर्ट समय जटिलता प्रश्न


इंसर्शन सॉर्ट की समय जटिलता

  • सर्वोत्तम स्थिति: O(n) - जब सरणी पहले से क्रमबद्ध हो
  • औसत/सबसे खराब स्थिति: O(n²)

विशेष पैटर्न वाली सरणी के लिए समय जटिलता

सरणी: 6, 5, 8, 7, 10, 9, ... i, i-1

यहां प्रत्येक जोड़ी स्वैप है। इंसर्शन सॉर्ट प्रत्येक जोड़ी को एक ऑपरेशन में ठीक कर देगा। इसलिए समय जटिलता O(n) होगी।

इंसर्शन सॉर्ट कोड

void insertionSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        int element = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > element) {
            arr[j + 1] = arr[j];
            j = j - 1;
        }
        arr[j + 1] = element;
    }
}
  1. - C++ में स्ट्रैंड सॉर्ट

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

  1. - C++ प्रोग्राम: इंसर्शन सॉर्ट लागू करना

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

  1. - C# में इंसर्शन सॉर्ट

    इंसर्शन सॉर्ट एक सॉर्टिंग एल्गोरिदम है जो एक समय में एक तत्व लेता है और उसे सरणी में उसकी सही स्थिति में डालता है। यह प्रक्रिया तब तक जारी रहती है जब तक सरणी क्रमबद्ध नहीं हो जाती। C# में इंसर्शन सॉर्ट को प्रदर्शित करने वाला एक प्रोग्राम निम्नलिखित है। उदाहरण using System; namespace InsertionSortD