प्रविष्टि क्रम की समय जटिलता क्या है?
समय की जटिलता इनपुट की मात्रा के एक फ़ंक्शन के रूप में संसाधित या चलाने के लिए कोड या एल्गोरिदम के एक सेट द्वारा लिए गए समय की मात्रा है।
सम्मिलन प्रकार के लिए, समय जटिलता क्रम O(n) की होती है अर्थात सर्वोत्तम स्थिति में n का बड़ा O। और औसत या सबसे खराब स्थिति में जटिलता क्रम O(n 2 .) की होती है )।
सॉर्टिंग की समय जटिलता क्या होगी जब इंसर्शन सॉर्ट एल्गोरिथम को निम्न फॉर्म के n आकार के एरे पर लागू किया जाता है:6, 5, 8, 7, 10, 9 …… I, i-1
उपरोक्त सरणी को छाँटने की समय जटिलता O (n) है। आइए इस एल्गोरिथम को ध्यान से देखें, यहां सभी जोड़ियों को उनकी मूल स्थिति से बदल दिया जाता है यानी तत्व 1 और तत्व 2 की स्थिति आपस में बदल जाती है, 3 और 4 को आपस में बदल दिया जाता है और इसी तरह। इसलिए, एल्गोरिथम को सॉर्ट करते समय इस एल्गोरिथम को सॉर्ट करने के लिए केवल एक ऑपरेशन 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;
}
}