2009-12-19 21 views
139

उपयोग के मामले क्या हैं जब किसी विशेष सॉर्टिंग एल्गोरिदम को दूसरों पर प्राथमिकता दी जाती है - merge sort बनाम quick sort बनाम heap sort बनाम intro sort, आदि?
प्रत्येक सॉर्टिंग एल्गोरिदम का उपयोग कब किया जाता है?

क्या आकार, डेटा संरचना, उपलब्ध स्मृति और कैश, और सीपीयू प्रदर्शन के आधार पर उनका उपयोग करने में एक अनुशंसित मार्गदर्शिका है?

+2

इस सामग्री के लिए http://bigocheatsheet.com/ जैसे एक गाइड greaaat –

उत्तर

41

डेटा और एल्गोरिदम के विभिन्न प्रकार के लिए एनिमेशन का एक सेट sorting-algorithms.com

+3

ठीक +1 होगा क्योंकि यह थोड़े शांत है। – GrayWizardx

+16

यह सवाल का जवाब नहीं देता है। –

+1

ठीक है, शायद यह करता है। –

3

क्या तुलना करने के लिए दिए गए लिंक/एनिमेशन जाता है जब डेटा की मात्रा उपलब्ध स्मृति से अधिक --- जिस पर डेटा के ऊपर से गुजरता की संख्या इंगित पर विचार नहीं करते, यानी आई/ओ-लागत, रनटाइम पर हावी है। यदि आपको ऐसा करने की ज़रूरत है, तो "बाहरी सॉर्टिंग" पर पढ़ें जो आम तौर पर विलय के प्रकारों को कवर करता है- और ढेर प्रकार।

http://corte.si/posts/code/visualisingsorting/index.html और http://corte.si/posts/code/timsort/index.html में विभिन्न सॉर्टिंग एल्गोरिदम की तुलना में कुछ अच्छी छवियां भी हैं।

20

क्विक्सोर्ट आमतौर पर औसत पर सबसे तेज़ होता है, लेकिन इसमें कुछ बहुत बुरा बुरा-मामला व्यवहार होता है। तो अगर आपको कोई बुरा डेटा गारंटी नहीं देनी है तो आपको O(N^2) मिलती है, आपको इससे बचना चाहिए।

मर्ज-सॉर्ट अतिरिक्त मेमोरी का उपयोग करता है, लेकिन बाहरी सॉर्टिंग के लिए विशेष रूप से उपयुक्त है (यानी बड़ी फाइलें जो स्मृति में फिट नहीं होती हैं)।

हीप-सॉर्ट जगह में सॉर्ट कर सकता है और सबसे खराब मामला वर्ग व्यवहार नहीं है, लेकिन ज्यादातर मामलों में औसत से क्विकॉर्ट की तुलना में धीमी है।

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

99% मामलों में, आप लाइब्रेरी के प्रकार के साथ ठीक होंगे, जो आमतौर पर क्विकॉर्ट पर आधारित होते हैं।

+4

+1: "99% मामलों में, आप लाइब्रेरी के प्रकार के साथ ठीक होंगे, जो आमतौर पर क्विकॉर्ट पर आधारित होते हैं"। –

+0

यादृच्छिक पिवोटिंग Quicksort को सभी व्यावहारिक उद्देश्यों के लिए O (nlogn) का रनटाइम देता है, बिना खराब डेटा के किसी भी गारंटी की आवश्यकता के। मुझे सच में नहीं लगता कि कोई भी किसी भी उत्पादन कोड के लिए ओ (एन^2) क्विकॉर्ट को लागू करता है। – MAK

+2

एमएके, सिवाय, सी मानक पुस्तकालय qsort? (Http://www.google.com/codesearch/p?hl=en&sa=N&cd=6&ct=rc#XAzRy8oK4zA/libc/stdlib/qsort.c&q=memmove%20android%20package:%22git://android.git। kernel.org/platform/bionic.git%22&d=1) - जिस पर "उत्पादन कोड" का अधिकतर हिस्सा –

251

सबसे पहले, यह एक परिभाषा है, क्योंकि यह बहुत महत्वपूर्ण है: स्थिर प्रकार वह है जो समान कुंजी वाले तत्वों को पुन: व्यवस्थित नहीं करने की गारंटी देता है।

अनुशंसाएँ:

त्वरित क्रमित करें: आप एक स्थिर प्रकार और औसत मामले प्रदर्शन की जरूरत नहीं है जब सबसे ज्यादा मामले प्रदर्शन की तुलना में अधिक मायने रखती है। एक त्वरित प्रकार ओ (एन लॉग एन) औसत पर, ओ (एन^2) सबसे खराब मामले में है। एक अच्छा कार्यान्वयन रिकर्सन के लिए स्टैक स्पेस के रूप में ओ (लॉग एन) सहायक भंडारण का उपयोग करता है।

सॉर्ट मर्ज करें: जब आपको स्थिर, ओ (एन लॉग एन) सॉर्ट की आवश्यकता होती है, तो यह आपके एकमात्र विकल्प के बारे में है। इसके लिए केवल डाउनसाइड्स यह है कि यह ओ (एन) सहायक अंतरिक्ष का उपयोग करता है और त्वरित प्रकार की तुलना में थोड़ा बड़ा स्थिर होता है। कुछ जगहों पर मर्ज प्रकार हैं, लेकिन AFAIK वे सभी ओ (एन लॉग एन) से स्थिर या बदतर नहीं हैं। यहां तक ​​कि ओ (एन लॉग एन) जगहों के प्रकार में सादे पुराने विलय प्रकार की तुलना में इतनी बड़ी स्थिरता है कि वे उपयोगी एल्गोरिदम की तुलना में अधिक सैद्धांतिक जिज्ञासा हैं।

हीप सॉर्ट: जब आपको स्थिर प्रकार की आवश्यकता नहीं होती है और आप औसत केस प्रदर्शन की तुलना में सबसे खराब केस प्रदर्शन के बारे में अधिक परवाह करते हैं। यह ओ (एन लॉग एन) होने की गारंटी है, और ओ (1) सहायक अंतरिक्ष का उपयोग करता है, जिसका अर्थ है कि आप अनपेक्षित रूप से बहुत बड़े इनपुट पर ढेर या ढेर स्थान से बाहर नहीं होंगे।

इंट्रोसोर्ट: यह एक त्वरित प्रकार है जो एक निश्चित रिकर्सन गहराई के बाद एक हीड़ प्रकार में स्विच करता है ताकि त्वरित प्रकार के ओ (एन^2) सबसे खराब मामले के आसपास हो सके। यह एक सादे पुराने त्वरित प्रकार से लगभग हमेशा बेहतर होता है, क्योंकि आपको गारंटीकृत ओ (एन लॉग एन) प्रदर्शन के साथ त्वरित प्रकार का औसत मामला मिलता है। शायद इसके बजाय एक हीप सॉर्ट का उपयोग करने का एकमात्र कारण गंभीर रूप से स्मृति बाधित सिस्टम में है जहां ओ (लॉग एन) स्टैक स्पेस व्यावहारिक रूप से महत्वपूर्ण है।

सम्मिलन क्रम: जब एन को छोटे होने की गारंटी दी जाती है, जिसमें त्वरित प्रकार के मूल मामले या मर्ज सॉर्ट शामिल हैं। हालांकि यह ओ (एन^2) है, यह बहुत छोटा स्थिर है और एक स्थिर प्रकार है।

बबल सॉर्ट, चयन क्रम: जब आप कुछ त्वरित और गंदे कर रहे होते हैं और किसी कारण से आप मानक लाइब्रेरी के सॉर्टिंग एल्गोरिदम का उपयोग नहीं कर सकते हैं। इन्हें सम्मिलन के प्रकार पर एकमात्र लाभ लागू करना थोड़ा आसान है।


गैर तुलना प्रकार: कुछ काफी सीमित स्थिति यह हे तोड़ने के लिए संभव है के तहत (एन लॉग ऑन एन) बाधा और प्रकार हे (एन) में। यहां कुछ ऐसे मामले दिए गए हैं जहां यह प्रयास करने योग्य है:

सॉर्टिंग प्रकार: जब आप सीमित सीमा के साथ पूर्णांक को सॉर्ट कर रहे हैं।

रैडिक्स सॉर्ट: जब लॉग (एन) के से काफी बड़ा है, जहां के रेडिक्स अंकों की संख्या है।

बाल्टी सॉर्ट: जब आप गारंटी दे सकते हैं कि आपका इनपुट लगभग समान रूप से वितरित किया गया है।

+1

जैसा कि मुझे याद है, हीप सॉर्ट में भी एक बहुत ही अनुमानित चलने का समय होता है जिसमें एक ही आकार के विभिन्न इनपुट के बीच बहुत भिन्नता होती है, लेकिन इसकी निरंतर अंतरिक्ष सीमा से कम ब्याज है। मुझे एन^2 प्रकारों को लागू करने के लिए सबसे आसान प्रविष्टि भी मिलती है, लेकिन शायद यह सिर्फ मुझे है। अंत में, आप शैल सॉर्ट का भी उल्लेख करना चाहेंगे, जो सम्मिलन प्रकार के रूप में लागू करने के लिए लगभग सरल है लेकिन बेहतर प्रदर्शन है, हालांकि अभी भी लॉग एन नहीं है। – JaakkoK

+24

मत भूलना [Bogosort] (http://en.wikipedia.org/wiki/Bogosort)! ;-) –

+2

+1 बहुत दिलचस्प है। क्या आप यह बताने की देखभाल करेंगे कि आप "गारंटी ... लगभग समान रूप से वितरित कैसे कर सकते हैं।" बाल्टी के लिए सॉर्ट करें? –

0

@dsimcha लिखा है: गिनती प्रकार: यदि आप एक सीमित रेंज के साथ पूर्णांकों छँटाई कर रहे हैं

मुझे लगता है कि करने के लिए बदल जाएगा:

गिनती प्रकार: जब आप प्रकार धनात्मक पूर्णांक (0 - पूर्णांक। कबूतर के कारण MAX_VALUE-2)।

आप हमेशा रैखिक समय में दक्षता हेरिस्टिक के रूप में अधिकतम और न्यूनतम मान प्राप्त कर सकते हैं।
इसके अलावा आपको इंटरमीडिएट सरणी के लिए कम से कम एन अतिरिक्त स्थान की आवश्यकता है और यह स्पष्ट रूप से स्थिर है।

/** 
* Some VMs reserve some header words in an array. 
* Attempts to allocate larger arrays may result in 
* OutOfMemoryError: Requested array size exceeds VM limit 
*/ 
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

देखें (भले ही यह वास्तव में MAX_VALUE -2 के लिए अनुमति देगा): Do Java arrays have a maximum size?

इसके अलावा, मैं समझा जाएगा कि मूलांक तरह जटिलता n कुंजी जो शब्द आकार के पूर्णांक हैं के लिए ओ (wn) है डब्ल्यू। कभी-कभी डब्ल्यू को निरंतर के रूप में प्रस्तुत किया जाता है, जो कि सर्वोत्तम तुलना-आधारित सॉर्टिंग एल्गोरिदम की तुलना में रेडिक्स सॉर्ट बेहतर (पर्याप्त रूप से बड़े एन के लिए) बनाता है, जो सभी एन कुंजी को सॉर्ट करने के लिए ओ (एन लॉग एन) तुलना करते हैं।हालांकि, सामान्य डब्ल्यू में निरंतर नहीं माना जा सकता है: यदि सभी एन कुंजी अलग हैं, तो यादृच्छिक-एक्सेस मशीन के लिए उन्हें कम से कम लॉग एन होना चाहिए ताकि वे स्मृति में उन्हें स्टोर कर सकें, जो कि समय-समय पर जटिलता देता है (एन लॉग एन)। (विकिपीडिया से)

संबंधित मुद्दे

 संबंधित मुद्दे