इस बुलबुला प्रकार व्युत्पन्न के सापेक्ष चलने का समय क्या है? सॉर्टिंग, बबल-सॉर्ट

public class Sort {
public static void sort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] > arr[i + 1]) {
/* swap */
int temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
/* make i == -1 because at the end of the loop, it increments to go to 0 */
i = -1;
}
}
}
}

यह एक पारंपरिक बबल सॉर्ट से अलग है। लेकिन क्या इसका समय खराब चल रहा है?

मेरा मानना ​​है कि यह अभी भी O (N ^ 2) है, इसलिए मैं यह नहीं देखता कि यह कैसे बदतर है ...

उत्तर:

मजेदार जानवर।

सबसे खराब स्थिति में चलें, एक छँटाई विरोधी इनपुट:

9 8 7 6 5 4 3 2 1

9 को पहली से अंतिम स्थिति में स्थानांतरित करने के लिए कितनी तुलनाओं की आवश्यकता है?
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 = (n-1) * (n-2) / 2

दूसरे को अंतिम स्थिति में 8 भेजने के बारे में क्या?
1 + 2 + 3 + 4 + 5 + 6 + 7 = (n-2) * (n-3) / 2

तो, आपका एल्गोरिथ्म वास्तव में है घन तुलना में प्रदर्शन किया!

फिर भी, सुरंग के अंत में एक प्रकाश है:
यह अभी भी प्रदर्शन किए गए स्वैप की संख्या में मानक बुलबुले की तरह केवल द्विघात है।

यह निश्चित रूप से बुलबुले का कार्यान्वयन है, हालांकि यह पारंपरिक एल्गोरिथ्म नहीं है। आप सही हैं, एल्गोरिथ्म O (n ^ 2) में है।

हालांकि यह एल्गोरिथम और पारंपरिक हैएल्गोरिथ्म असममित जटिलता के संदर्भ में समान हैं, एक वास्तविक मशीन पर चलने का समय अलग हो सकता है। याद रखें कि जब हम O (जो भी) जटिलता देख रहे हैं, तब लगातार कारक छोड़े जाते हैं। इसलिए

O(3 n^2) = O(n^2)

ध्यान रखें कि ओ (जो भी) हैं कार्यों के सेट

पारंपरिक बुलबुले पर विचार करें: यहां आप सरणी इंडेक्स को लगातार बढ़ाकर पूरे सरणी से गुजरते हैं। इस एल्गोरिथ्म में आप कुछ ऐसी तुलनाएँ करते हैं, जिनकी वास्तव में ज़रूरत नहीं होती है (क्योंकि आप जानते हैं कि जब आप लूप के लिए बाहरी के लूप वेरिएबल को बढ़ाते हैं (पारंपरिक बुलबुले में आपके पास छोरों के लिए 2 हैं), तो आप जानते हैं कि बाईं ओर सब कुछ पहले से ही हल है। तो आप फिर से उस पर लूप नहीं करेंगे।

व्यवहार में, इससे शायद कोई फर्क नहीं पड़ेगा क्योंकि एल्गोरिथम को इतना समय चाहिए होगा कि आप इससे प्रभावित होने से पहले ही उससे तंग आ जाएंगे।