जब मैं देशी sort विधि का उपयोग कर एक ऐरे सॉर्ट करता हूं, तो रूबी किस एल्गोरिदम का उपयोग करता है?रूबी की सॉर्ट विधि किस एल्गोरिदम का उपयोग करती है?
क्या यह डेटा-निर्भर है, यानी, यदि डेटा छोटा है तो यह एक्स एल्गोरिदम का उपयोग करता है अन्यथा यह वाई एल्गोरिदम का उपयोग करता है?
क्या यह एक स्थिर प्रकार है? औसत समय जटिलता क्या है?
यहाँ देखो: जो एन लॉग इन करें n औसतन जटिलता है http://www.igvita.com/2009/03/26/ruby-algorithms-sorting-trie-heaps/
यह देशी रूप तथापि quicksort का उपयोग करता है,।
इसका यह भी अर्थ है कि यह एक स्थिर प्रकार की संभावना नहीं है। Http://en.wikipedia.org/wiki/Quick_sort –
पर इसकी स्पष्टीकरण देखें, विशेष रूप से यदि सरणी लगभग क्रमबद्ध है, तो त्वरित प्रकार की जटिलता n^2 बन जाती है। फिर भी, ज्यादातर मामलों में यह बेहद तेज़ है। – AlbertoPL
यदि सरणी लगभग क्रमबद्ध है, तो केवल एक बेवकूफ quicksort n^2 पर जाता है। तीन पिवट चयन का औसत सभी कार्यान्वयन में है, मैंने –
रुबी के प्रकार की स्थिरता को [इस प्रश्न] में संबोधित किया गया है (https://stackoverflow.com/questions/15442298/is-sort-in-ruby-stable)। –