जावा की Arrays.sort विधि विभिन्न प्रकार के लिए दो अलग सॉर्टिंग एल्गोरिदम का उपयोग क्यों करती है?

Question

जावा की Arrays.sort विधि प्राइमेटिव के सरणी के लिए क्विक्सोर्ट का उपयोग करती है और वस्तुओं के सरणी के लिए क्रमबद्ध करती है। मेरा मानना ​​है कि अधिकांश समय क्विक्सोर्ट विलय की तुलना में तेज़ है और कम मेमोरी खर्च करता है। मेरे प्रयोग इसका समर्थन करते हैं, हालांकि दोनों एल्गोरिदम ओ (एन लॉग (एन) हैं)। तो अलग-अलग प्रकार के लिए अलग-अलग एल्गोरिदम क्यों उपयोग किए जाते हैं?

Answer 1

सबसे संभावित कारण: quicksort स्थिर नहीं है, यानी समान प्रविष्टियां इस प्रकार के दौरान अपनी सापेक्ष स्थिति बदल सकती हैं; अन्य चीजों के साथ, इसका मतलब यह है कि यदि आप पहले से सॉर्ट किए गए सरणी को सॉर्ट करते हैं, तो यह अपरिवर्तित नहीं रह सकता है।

चूंकि आदिम प्रकारों की कोई पहचान नहीं है (एक ही मूल्य के साथ दो चींटियों को अलग करने का कोई तरीका नहीं है), इससे कोई फर्क नहीं पड़ता। लेकिन संदर्भ प्रकारों के लिए, यह कुछ अनुप्रयोगों के लिए समस्याएं पैदा कर सकता है। इसलिए, उन लोगों के लिए एक स्थिर विलय प्रकार का उपयोग किया जाता है।

ओटीओएच, उपयोग करने के लिए एक कारण (गारंटीकृत एन * लॉग (एन)) आदिम प्रकारों के लिए विलय प्रकार हो सकता है कि यह सरणी के क्लोन बनाने की आवश्यकता हो। संदर्भ प्रकारों के लिए, जहां संदर्भित वस्तुएं आमतौर पर संदर्भों की सरणी की तुलना में कहीं अधिक स्मृति लेती हैं, यह आम तौर पर कोई फर्क नहीं पड़ता। लेकिन प्राचीन प्रकार के लिए, सरणी को क्लोन करने से स्मृति उपयोग को दोगुना कर दिया जाता है।

Answer 2

एक कारण यह है कि मैं के बारे में सोच सकते हैं, जबकि mergesort हे की सबसे खराब स्थिति समय (n लॉग एन) को बरकरार रखे हुए quicksort हे की एक सबसे खराब स्थिति समय जटिलता (n^2) किया है। ऑब्जेक्ट एरे के लिए एक उचित उम्मीद है कि कई डुप्लिकेट ऑब्जेक्ट संदर्भ होंगे जो एक ऐसा मामला है जहां क्विकॉर्ट सबसे खराब होता है।

एक सभ्य visual comparison of various algorithms है, विभिन्न एल्गोरिदम के लिए दाएं सबसे अधिक ग्राफ पर विशेष ध्यान दें।

Answer 3

मैं एल्गोरिथम पर व्याख्यान प्रोफेसर बॉब Sedgewick जावा प्रणाली प्रकार के लिए मूल्यांकन उल्लेख में से एक में Coursera वर्ग ले रहा था:

"एक प्रोग्रामर वस्तुओं का उपयोग कर रहा है, तो हो सकता है अंतरिक्ष नहीं एक गंभीर रूप से महत्वपूर्ण है मर्ज सॉर्ट द्वारा उपयोग की जाने वाली अतिरिक्त जगह और कोई समस्या नहीं है। और यदि कोई प्रोग्रामर आदिम प्रकार का उपयोग कर रहा है, तो शायद प्रदर्शन सबसे महत्वपूर्ण बात है ताकि वे त्वरित प्रकार का उपयोग कर सकें। "

Answer 4

जावा 7 एपीआई वस्तु सरणियों के लिए this answer, Arrays#Sort() में उद्धृत डॉक्स के अनुसार अब TimSort का उपयोग करता है, जो MergeSort और InsertionSort के एक संकर है। दूसरी ओर, Arrays#sort() आदिम सरणी के लिए अब Dual-Pivot QuickSort का उपयोग करता है। इन परिवर्तनों को जावा SE में शुरू से लागू किया गया 7.

Answer 5

जावा के Arrays.sort विधि quicksort, प्रविष्टि प्रकार और mergesort उपयोग करता है। ओपनजेडीके कोड में कार्यान्वित एक एकल और दोहरी पिवोट क्विकॉर्ट भी है। सबसे तेज़ सॉर्टिंग एल्गोरिदम परिस्थितियों पर निर्भर करता है और विजेता हैं: छोटे सरणी (47 वर्तमान में चुने गए) के लिए सम्मिलन क्रम, ज्यादातर क्रमबद्ध सरणी के लिए विलय, और शेष सरणी के लिए क्विकॉर्ट, ताकि जावा के Array.sort() को सर्वोत्तम एल्गोरिदम चुनने का प्रयास किया जा सके उन मानदंडों के आधार पर आवेदन करें।