Timsort सॉर्ट एल्गोरिथम

Timsort , किसी भी "बुलबुले" और "आवेषण" के विपरीत, एक अपेक्षाकृत नई बात है - यह 2002 में टिम पीटर्स (उनके नाम पर) द्वारा आविष्कार किया गया था। तब से, यह पहले से ही पायथन, ओपनजेडके 7 और एंड्रॉइड जेडडीके 1.5 में मानक सॉर्टिंग एल्गोरिदम बन गया है। और यह समझने के लिए कि क्यों - सिर्फ विकिपीडिया से इस प्लेट को देखें।



पहली नज़र में, तालिका में विशाल चयन, औसत और सबसे खराब स्थिति में केवल 7 पर्याप्त एल्गोरिदम (जटिलता ओ (एन लोगन) के साथ) हैं, जिनमें से केवल 2 सर्वश्रेष्ठ स्थिति में स्थिरता और जटिलता ओ (एन) का दावा कर सकते हैं। इन दोनों में से एक एक लंबे समय के लिए प्रसिद्ध "सॉर्टिंग यूज बाईनरी ट्री" है । लेकिन दूसरा एक ही Timsort है।

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

सीधे मुद्दे पर

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

1. एक विशेष एल्गोरिथ्म द्वारा, हम इनपुट सरणी को उप-वर्गों में विभाजित करते हैं।
2. हम आवेषण द्वारा सामान्य रूप से छँटाई करके प्रत्येक सबरे को सॉर्ट करते हैं।
3. हम संशोधित मर्ज सॉर्ट का उपयोग करके एकल सरणी में सॉर्ट किए गए उप-संग्रह को इकट्ठा करते हैं।

शैतान, हमेशा की तरह, विवरण में छुपा है, पैरा 1 से एल्गोरिथ्म में और अनुच्छेद 3 के मर्ज के प्रकार में संशोधन।

एल्गोरिथ्म

प्रयुक्त अवधारणाएँ

• एन - इनपुट सरणी आकार
• रन इनपुट सरणी में एक आदेशित सबरे है। इसके अलावा, आदेश या गैर-चढ़ते आरोही, या सख्ती से उतरते हुए। यही है, या तो "a0 <= a1 <= a2 <= ...", या "a0> a1> a2> ..."
• minrun - जैसा कि ऊपर बताया गया है, एल्गोरिथ्म के पहले चरण में, इनपुट ऐरे को सबरेज़ में विभाजित किया जाएगा। मिनरन इस तरह के सबर्रे का न्यूनतम आकार है। इस संख्या की गणना N के एक निश्चित तर्क द्वारा की जाती है ।

चरण 0. मिनरन की गणना ।

निम्नलिखित सिद्धांतों के आधार पर संख्या minrun N के आधार पर निर्धारित की जाती है :

1. यह बहुत बड़ा नहीं होना चाहिए, क्योंकि भविष्य में सम्मिलन छँटाई को माइनरन आकार के सबर्रे पर लागू किया जाएगा, और यह केवल छोटे सरणियों पर प्रभावी होगा
2. यह बहुत छोटा नहीं होना चाहिए, क्योंकि जितना छोटा सबर्रे होता है, उतने ही मर्जिंग सबरेज़ को एल्गोरिथम के अंतिम चरण में करना होगा।
3. यह अच्छा होगा यदि N \ minrun 2 की शक्ति थी (या इसके करीब)। यह आवश्यकता इस तथ्य के कारण है कि मर्जिंग एल्गोरिथ्म के लिए एल्गोरिथ्म लगभग समान आकार के सबरेज़ पर सबसे अधिक कुशलता से काम करता है।

इस बिंदु पर, एल्गोरिथ्म के लेखक अपने स्वयं के प्रयोगों को संदर्भित करते हैं, जिसमें दिखाया गया है कि minrun > 256 बिंदु 1 का उल्लंघन किया जाता है, minrun <8 - बिंदु 2 का उल्लंघन किया जाता है और यह रेंज (32; 65) से मूल्यों का उपयोग करने के लिए सबसे अधिक कुशल है। अपवाद है अगर N <64, तो minrun = N और टाइमसॉर्ट एक साधारण प्रविष्टि प्रकार में बदल जाता है। फिलहाल, मिनरन गणना एल्गोरिथ्म बस अपमानजनक है: हम एन से सबसे महत्वपूर्ण 6 बिट्स लेते हैं और एक को जोड़ते हैं यदि शेष कम से कम महत्वपूर्ण बिट्स में कम से कम एक नॉनजरो हो। नमूना कोड इस तरह दिखता है:

int GetMinrun(int n) { int r = 0; /*  1        1  */ while (n >= 64) { r |= n & 1; n >>= 1; } return n + r; } 

चरण 1. उपग्रहों में विभाजित करना और उन्हें क्रमबद्ध करना।

तो, इस स्तर पर, हमारे पास एक इनपुट ऐरे, उसका आकार N और परिकलित संख्या मिनरन है । इस चरण की एल्गोरिथ्म:

1. हमने इनपुट सरणी की शुरुआत में वर्तमान तत्व के सूचक को रखा।
2. वर्तमान तत्व से शुरू होकर, हम रन के लिए इनपुट ऐरे में देखते हैं (एक ऑर्डर किया गया सबर्रे)। परिभाषा के अनुसार, इस रन में स्पष्ट रूप से वर्तमान तत्व और अगला एक शामिल होगा, लेकिन आगे यह पहले से ही भाग्यशाली है। यदि परिणामी सबर्रे को अवरोही क्रम में आदेश दिया जाता है, तो हम तत्वों को पुनर्व्यवस्थित करते हैं ताकि वे आरोही क्रम में जाएं (यह एक सरल रेखीय एल्गोरिथ्म है, बस दोनों सिरों से मध्य तक जाते हैं, तत्वों की अदला-बदली करते हैं)।
3. यदि चालू रन का आकार ' माइनरन से कम है - हम मिनरन की मात्रा में रन थ्रेड (आकार) के बाद पाए गए तत्वों को लेते हैं । इस प्रकार, उत्पादन में हमें आकार मीनार या बड़े का एक हिस्सा मिलता है, जिसका कुछ हिस्सा (और आदर्श रूप से यह सब) का आदेश दिया जाता है।
4. हम इस सबर्रे में छंटनी को लागू करते हैं। चूँकि सबर्रे का आकार छोटा होता है और इसका हिस्सा पहले से ही क्रमबद्ध होता है - छँटाई जल्दी और कुशलता से काम करता है।
5. हमने पॉइंटर को वर्तमान तत्व में सबर्रे तत्व के बगल में रखा।
6. यदि इनपुट ऐरे का अंत नहीं हुआ है - चरण 2 पर जाएं, अन्यथा - इस चरण का अंत।

चरण 2. विलय।

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

1. लगभग बराबर आकार (यह अधिक कुशल है) की उपमाओं को मिलाएं।
2. एल्गोरिथ्म को स्थिर रखें - अर्थात अर्थहीन क्रमपरिवर्तन न करें (उदाहरण के लिए, स्थानों में दो लगातार समरूप संख्याओं को स्वैप न करें)।

इसे इस तरह से हासिल किया जाता है।

1. जोड़े का एक खाली स्टैक बनाएं <सबर्रे की शुरुआत का इंडेक्स> - <सबर्रे का आकार>। पहले आदेश दिया सबर्रे लो।
2. स्टैक में जोड़ें डेटा की एक जोड़ी <स्टार्ट इंडेक्स> - <आकार> वर्तमान सबर्रे के लिए।
3. निर्धारित करें कि क्या पिछले के साथ वर्तमान सबर्रे को मर्ज करना है। इसके लिए, 2 नियमों के कार्यान्वयन की जाँच की जाती है (एक्स, वाई और जेड सूक्ष्मता के ढेर में शीर्ष तीन के आकार होने दें):
   X> Y + Z
   य> ज़
4. यदि किसी एक नियम का उल्लंघन किया जाता है, तो Y सरणी X और Z सरणियों के छोटे के साथ विलीन हो जाती है। यह तब तक दोहराया जाता है जब तक कि दोनों नियम पूरे नहीं होते हैं या डेटा पूरी तरह से आदेशित नहीं होता है।
5. यदि अभी भी उप-विचार नहीं किए जाते हैं, तो हम अगले एक को लेते हैं और चरण 2 पर जाते हैं। अन्यथा, अंत।

इस मुश्किल प्रक्रिया का उद्देश्य संतुलन बनाए रखना है। यानी परिवर्तन इस तरह दिखेगा:

जिसका अर्थ है कि स्टैक में सबरेज़ का आकार आगे मर्ज की छंटाई के लिए प्रभावी है। एक आदर्श मामले की कल्पना करें: हमारे पास आकार 128, 64, 32, 16, 8, 4, 2, 2 की उप-परतें हैं (हम आवश्यकता के बारे में एक सेकंड के लिए भूल जाते हैं " सबर्रे आकार> = माइनरन ")। इस मामले में, किसी भी विलय को तब तक निष्पादित नहीं किया जाएगा, जब तक कि अंतिम 2 सबरेज़ को पूरा नहीं किया जाता है, लेकिन उसके बाद 7 पूरी तरह से संतुलित विलय निष्पादित किए जाएंगे।

सबर्रे मर्ज प्रक्रिया

जैसा कि आपको याद है, एल्गोरिथम के दूसरे चरण में हम दो सबरेज को एक ऑर्डर किए गए एक में विलय कर रहे हैं। हम हमेशा 2 लगातार सबरेज़ को जोड़ते हैं। उन्हें मर्ज करने के लिए, अतिरिक्त मेमोरी का उपयोग किया जाता है।

1. हम कनेक्ट किए गए सबरेज़ के छोटे आकार में एक अस्थायी सरणी बनाते हैं।
2. एक छोटे सरणी के लिए सबरेज़ की प्रतिलिपि बनाएँ
3. हमने वर्तमान स्थिति बिंदुओं को एक बड़े और अस्थायी सरणी के पहले तत्वों पर रखा है।
4. प्रत्येक अगले चरण में, हम बड़े और अस्थायी सरणियों में वर्तमान तत्वों के मूल्य पर विचार करते हैं, उनमें से छोटे को लेते हैं और इसे एक नए क्रमबद्ध सरणी में कॉपी करते हैं। हम उस सरणी में वर्तमान तत्व के सूचक को स्थानांतरित करते हैं जिसमें से तत्व लिया गया था।
5. जब तक कि सरणियों में से एक समाप्त न हो जाए तब तक 4 दोहराएं।
6. शेष सरणी के सभी तत्वों को नए सरणी के अंत में जोड़ें।

मर्जिंग सबरेज़ के लिए प्रक्रिया का संशोधन

ऊपर दिखाए गए मर्ज एल्गोरिथम में सब कुछ अच्छा लगता है। सिवाय एक के। ऐसी दो सरणियों के विलय के लिए एक प्रक्रिया की कल्पना करें:
A = {1, 2, 3, ..., 9999, 10000}
B = {20000, 20001, ...., 29999, 30000}
उनके लिए उपरोक्त प्रक्रिया, निश्चित रूप से, काम करेगी, लेकिन हर बार इसके चौथे पैराग्राफ पर आपको एक तुलना और एक प्रति निष्पादित करने की आवश्यकता होगी। और वह 10,000 तुलना और 10,000 प्रतियां। Timsort एल्गोरिथ्म इस जगह में एक संशोधन की पेशकश करता है जिसे वह सरपट कहता है। नीचे पंक्ति है:

1. हम मर्ज प्रक्रिया शुरू करते हैं, जैसा कि ऊपर दिखाया गया है।
2. एक अस्थायी या बड़े सबर्रे से एक तत्व की प्रतिलिपि बनाने के प्रत्येक ऑपरेशन में जिसके परिणामस्वरूप, हमें याद है कि तत्व कौन सा था।
3. यदि पहले से ही तत्वों की एक निश्चित संख्या (एल्गोरिथम के कार्यान्वयन में यह संख्या कठोरता से 7 के बराबर है) एक ही सरणी से ली गई थी - हम मानते हैं कि हमें इससे आगे डेटा लेना होगा। इस विचार की पुष्टि करने के लिए, हम सरपट मोड में स्विच करते हैं, अर्थात। हम बाइनरी सर्च द्वारा डेटा के अगले बड़े हिस्से की आपूर्ति के लिए उम्मीदवार ऐरे के माध्यम से दौड़ेंगे (हमें याद है कि एरे को ऑर्डर किया गया है और हमारे पास बाइनरी सर्च का हर अधिकार है) दूसरे ऐरे से कनेक्ट होना है। बाइनरी खोज रैखिक की तुलना में अधिक कुशल है, और इसलिए खोज संचालन बहुत कम होगा।
4. आखिरकार वह क्षण मिल गया जब करंट प्रोवाइडर एरे से डेटा अब हमें सूट नहीं करता (या एरे के अंत तक पहुंचकर), हम आखिरकार उन सभी को एक साथ कॉपी कर सकते हैं (जो एकल तत्वों की नकल करने से अधिक कुशल हो सकते हैं)।

शायद स्पष्टीकरण थोड़ा धूमिल है, आइए एक उदाहरण का प्रयास करें।
A = {1, 2, 3, ..., 9999, 10000}
B = {20000, 20001, ...., 29999, 30000}

1. पहले 7 पुनरावृत्तियों, हम संख्या ए , संख्या 20,000 से 1, 2, 3, 4, 5, 6 और 7 की तुलना करते हैं, और यह सुनिश्चित करते हुए कि 20,000 अधिक, परिणामस्वरूप A के लिए सरणी A के तत्वों की प्रतिलिपि बनाते हैं।
2. अगले पुनरावृत्ति से शुरू होकर, हम "सरपट" मोड पर स्विच करते हैं: हम 8, 10, 14, 22, 38, n + 2 ^ i ..., तत्वों की तुलना करते हैं, उत्तराधिकार में संख्या ए के 10000 ए के साथ 10000 ए । जैसा कि आप देख सकते हैं, ऐसी तुलना 10,000 से बहुत कम होगी।
3. हमें सरणी A के अंत में मिला और हम जानते हैं कि यह B से छोटा है (हम बीच में कहीं रुक भी सकते हैं)। सरणी ए से आवश्यक डेटा को परिणामस्वरूप एक पर कॉपी करें, और आगे बढ़ें।

वह पूरा एल्गोरिथ्म है।

संबंधित सामग्री

• विकिपीडिया पर Timsort (कोई रूसी संस्करण नहीं)
• इसके निर्माता से एल्गोरिथ्म की प्रस्तुति
• Stackoverflow पर एल्गोरिथम चर्चा
• एल्गोरिदम का सुंदर दृश्य