टिमसॉर्ट: Difference between revisions

टिमसॉर्ट
Class	Sorting algorithm
Data structure	Array
Worst-case performance
Best-case performance
Average performance
Worst-case space complexity

Revision as of 23:28, 16 July 2023

टिमसॉर्ट एक हाइब्रिड, स्थिर सॉर्टिंग एल्गोरिदम है, जो मर्ज सॉर्ट और इंसर्शन सॉर्ट से प्राप्त होता है, जिसे कई प्रकार के वास्तविक दुनिया के डेटा पर अच्छा प्रदर्शन करने के लिए डिज़ाइन किया गया है। इसे टिम पीटर्स द्वारा 2002 में पायथन प्रोग्रामिंग भाषा में उपयोग के लिए लागू किया गया था। एल्गोरिथम पहले से ऑर्डर किए गए डेटा के अनुक्रमों को ढूंढता है (चलता है) और शेष को अधिक कुशलता से क्रमबद्ध करने के लिए उनका उपयोग करता है। यह कुछ मानदंडों को पूरा होने तक रनों को मर्ज (संयोजित) करके किया जाता है। संस्करण 2.3 से टिम्सोर्ट पायथन का मानक सॉर्टिंग एल्गोरिदम रहा है।^[4] इसका उपयोग एंड्रॉइड ^[5] प्लेटफॉर्म पर जावा एसई 7, जीएनयू ऑक्टेव में^[6], वी8^[7] पर, स्विफ्ट,^[8] और रस्ट^[9] में गैर-आदिम प्रकार के सरणियों को सॉर्ट करने के लिए भी किया जाता है। 9]

यह पीटर मैकिलरॉय के 1993 के पेपर "ऑप्टिमिस्टिक सॉर्टिंग एंड इंफॉर्मेशन थियोरेटिक कॉम्प्लेक्सिटी" की तकनीकों का उपयोग करता है।^[10]

संक्रिया

टिमसॉर्ट को लगातार क्रम किए गए तत्वों के रन का लाभ उठाने के लिए डिज़ाइन किया गया था जो पहले से ही अधिकांश वास्तविक दुनिया के डेटा, प्राकृतिक रन में मौजूद हैं। यह डेटा एकत्र करने वाले तत्वों को रन में पुनरावृत्त करता है और साथ ही उन रन को स्टैक में रखता है। जब भी स्टैक के शीर्ष पर रन मर्ज मानदंड से मेल खाते हैं, तो वे मर्ज हो जाते हैं। यह तब तक चलता रहता है जब तक सभी डेटा का पता नहीं लगा लिया जाता है; फिर, सभी रन एक समय में दो रन में विलय हो जाते हैं और केवल एक क्रमबद्ध रन बचता है। निश्चित आकार की उप-सूचियों को मर्ज करने के बजाय ऑर्डर किए गए रन को मर्ज करने का लाभ यह है कि यह पूरी सूची को क्रमबद्ध करने के लिए आवश्यक तुलनाओं की कुल संख्या को कम कर देता है।

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

मर्ज मानदंड

रन को स्टैक (डेटा संरचना) में डाला जाता है। अगर |Z| ≤ |Y| + |X|, फिर X और Y को मर्ज कर दिया जाता है और स्टैक पर प्रतिस्थापित कर दिया जाता है। इस प्रकार, विलय तब तक जारी रहता है जब तक कि सभी रन संतुष्ट न हो जाएं i. |Z| > |Y| + |X| और ii. |Y| > |X|.

टिमसॉर्ट एक स्थिर सॉर्टिंग एल्गोरिदम है (समान कुंजी वाले तत्वों का क्रम रखा जाता है) और संतुलित मर्ज करने का प्रयास करता है (इस प्रकार एक मर्ज समान आकार के रन को मर्ज करता है)।

सॉर्टिंग स्थिरता प्राप्त करने के लिए, केवल लगातार रन मर्ज किए जाते हैं। दो गैर-क्रमिक रन के बीच, रन के अंदर एक ही कुंजी वाला एक तत्व हो सकता है। उन दो रन को मिलाने से समान कुंजियों का क्रम बदल जाएगा। इस स्थिति का उदाहरण ([] रन क्रमबद्ध हैं): [1 2 2] 1 4 2 [0 1 2]

एक संतुलित मर्ज की खोज में, टाइमसॉर्ट स्टैक के शीर्ष पर तीन रन, X, Y, Z पर विचार करता है, और अपरिवर्तनीय को संरक्षित करता है:

|Z| > |Y| + |X|
|Y| > |X|^[11]

यदि इनमें से किसी भी अपरिवर्तनीय का उल्लंघन किया जाता है, तो Y को X या Z में से छोटे के साथ विलय कर दिया जाता है और अपरिवर्तनीयों की दोबारा जाँच की जाती है। एक बार जब अपरिवर्तनीय पकड़ में आ जाते हैं, तो डेटा में एक नए रन की खोज शुरू हो सकती है।^[12] संतुलन के लिए विलय में देरी, कैश मेमोरी में रनों की ताज़ा घटना का फायदा उठाने और मर्ज निर्णयों को अपेक्षाकृत सरल बनाने के बीच समझौता बनाए रखते हुए ये अपरिवर्तनीय मर्ज को लगभग संतुलित बनाए रखते हैं।

मर्ज स्पेस ओवरहेड

मर्ज करने के लिए, टिमसॉर्ट छोटे ऐरे (इस चित्रण में X) के तत्वों को अस्थायी मेमोरी में कॉपी करता है, फिर तत्वों को अंतिम क्रम में X और Y के संयुक्त स्थान में सॉर्ट और भरता है।

मूल मर्ज सॉर्ट कार्यान्वयन यथास्थान नहीं है और इसमें N (डेटा आकार) का एक अतिरिक्त स्थान है। इन-प्लेस मर्ज सॉर्ट कार्यान्वयन मौजूद हैं, लेकिन इसमें काफी समय लगता है। एक मध्य अवधि प्राप्त करने के लिए, टिमसॉर्ट एन की तुलना में छोटे समय ओवरहेड और छोटे स्थान ओवरहेड के साथ मर्ज सॉर्ट करता है।

सबसे पहले, टिमसॉर्ट उस स्थान को ढूंढने के लिए एक बाइनरी खोज करता है जहां दूसरे रन का पहला तत्व पहले ऑर्डर किए गए रन में डाला जाएगा, इसे क्रम में रखते हुए। फिर, यह उस स्थान को ढूंढने के लिए उसी एल्गोरिदम को निष्पादित करता है जहां पहले रन का अंतिम तत्व दूसरे ऑर्डर किए गए रन में डाला जाएगा, इसे क्रम में रखते हुए। इन स्थानों के पहले और बाद के तत्व पहले से ही अपने सही स्थान पर हैं और उन्हें विलय की आवश्यकता नहीं है। फिर, दो रन के शेष तत्वों में से छोटे को अस्थायी मेमोरी में कॉपी किया जाता है, और तत्वों को अब खाली स्थान में बड़े रन के साथ विलय कर दिया जाता है। यदि पहला रन छोटा है, तो मर्ज शुरुआत में ही प्रारंभ हो जाता है; यदि दूसरा छोटा है, तो मर्ज अंत में प्रारंभ होता है। यह अनुकूलन सामान्य स्थिति में आवश्यक तत्व आंदोलनों की संख्या, चलने का समय और अस्थायी स्थान ओवरहेड को कम कर देता है।

उदाहरण: दो रन [1, 2, 3, 6, 10] और [4, 5, 7, 9, 12, 14, 17] को मिलाना होगा। ध्यान दें कि दोनों रन पहले से ही व्यक्तिगत रूप से क्रमबद्ध हैं। दूसरे रन का सबसे छोटा तत्व 4 है और इसके क्रम को संरक्षित करने के लिए इसे पहले रन के चौथे स्थान पर जोड़ना होगा (यह मानते हुए कि रन की पहली स्थिति 1 है)। पहले रन का सबसे बड़ा तत्व 10 है और इसका क्रम बनाए रखने के लिए इसे दूसरे रन के पांचवें स्थान पर जोड़ना होगा। इसलिए, [1, 2, 3] और [12, 14, 17] पहले से ही अपनी अंतिम स्थिति में हैं और वे रन जिनमें तत्वों की गति की आवश्यकता होती है वे हैं [6, 10] और [4, 5, 7, 9]। इस ज्ञान के साथ, हमें केवल 4 के बजाय आकार 2 का अस्थायी बफर आवंटित करने की आवश्यकता है।

मर्ज दिशा

मर्ज दोनों दिशाओं में किया जा सकता है: बाएं से दाएं, पारंपरिक मर्जसॉर्ट की तरह, या दाएं से बाएं।

मर्ज के दौरान सरपट दौड़ने वाला मोड

तत्वों (नीले तीर द्वारा इंगित) की तुलना की जाती है और छोटे तत्व को उसकी अंतिम स्थिति (लाल तीर द्वारा इंगित) पर ले जाया जाता है।

रन R1 और R2 का एक व्यक्तिगत विलय एक रन से चुने गए लगातार तत्वों की गिनती रखता है। जब यह संख्या न्यूनतम सरपट दौड़ने की सीमा (min_gallop) तक पहुंच जाती है, तो टिमसॉर्ट का मानना है कि यह संभावना है कि उस रन से अभी भी कई लगातार तत्वों का चयन किया जा सकता है और सरपट मोड में स्विच किया जा सकता है। आइए मान लें कि R1 इसे ट्रिगर करने के लिए ज़िम्मेदार है। इस मोड में, एल्गोरिदम रन R1 में रन R2 के अगले तत्व x के लिए एक घातीय खोज करता है, जिसे सरपट खोज के रूप में भी जाना जाता है। यह दो चरणों में किया जाता है: पहले चरण में सीमा का पता लगाया जाता है (2^क − 1, 2^k+1 - 1) जहां x है। दूसरा चरण पहले चरण में पाई गई सीमा में तत्व x के लिए बाइनरी खोज करता है। सरपट मोड रन में तत्वों के बीच अंतराल के पैटर्न के अनुसार मर्ज एल्गोरिदम को अनुकूलित करने का एक प्रयास है।

सभी लाल तत्व नीले से छोटे हैं (यहाँ, 21)। इस प्रकार उन्हें एक टुकड़े में अंतिम सरणी में ले जाया जा सकता है।

सरपट दौड़ना हमेशा कारगर नहीं होता. कुछ मामलों में सरपट दौड़ने वाले मोड में साधारण रैखिक खोज की तुलना में अधिक तुलना की आवश्यकता होती है। डेवलपर द्वारा किए गए बेंचमार्क के अनुसार, सरपट दौड़ना तभी फायदेमंद होता है जब एक रन का प्रारंभिक तत्व दूसरे रन के पहले सात तत्वों में से एक न हो। इसका तात्पर्य 7 की प्रारंभिक सीमा से है। सरपट दौड़ने वाले मोड की कमियों से बचने के लिए, दो क्रियाएं की जाती हैं: (1) जब सरपट दौड़ने को बाइनरी खोज एल्गोरिदम की तुलना में कम कुशल पाया जाता है, तो सरपट मोड से बाहर निकल जाता है। (2)

सरपट दौड़ने की सफलता या विफलता का उपयोग min_gallop को समायोजित करने के लिए किया जाता है। यदि चयनित तत्व उसी सरणी से है जिसने पहले एक तत्व लौटाया था, तो min_gallop एक से कम हो जाता है, इस प्रकार सरपट मोड में वापसी को प्रोत्साहित किया जाता है। अन्यथा, मूल्य एक से बढ़ जाता है, इस प्रकार सरपट मोड में वापसी को हतोत्साहित करता है। यादृच्छिक डेटा के मामले में, min_gallop का मान इतना बड़ा हो जाता है कि सरपट मोड की पुनरावृत्ति कभी नहीं होती है।^[13]

अवरोही रन

अवरोही क्रम में क्रमबद्ध डेटा का लाभ उठाने के लिए, टिमसॉर्ट उन्हें मिलने पर कड़ाई से अवरोही रन को उलट देता है और उन्हें रन के ढेर में जोड़ देता है। चूंकि अवरोही रन को बाद में आँख बंद करके उलट दिया जाता है, समान तत्वों वाले रन को छोड़कर एल्गोरिदम की स्थिरता बनी रहती है; यानी, समान तत्वों को उलटा नहीं किया जाएगा।

न्यूनतम रन आकार

टिम्सोर्ट एल्गोरिदम अपने प्रकार को निष्पादित करने के लिए न्यूनतम आकार के आदेशित अनुक्रमों, मिनरन की खोज करता है।

क्योंकि विलय तब सबसे अधिक कुशल होता है जब रनों की संख्या दो की शक्ति के बराबर या उससे थोड़ी कम होती है, और विशेष रूप से कम कुशल होती है जब रनों की संख्या दो की शक्ति से थोड़ी अधिक होती है, यह सुनिश्चित करने का प्रयास करने के लिए टिमसॉर्ट मिनरुन को चुनता है पूर्व स्थिति.^[11]

मिनरुन को 32 से 64 समावेशी श्रेणी में से चुना जाता है, जैसे कि डेटा का आकार, मिनरुन द्वारा विभाजित, दो की शक्ति के बराबर या उससे थोड़ा कम होता है। अंतिम एल्गोरिदम सरणी के आकार के छह सबसे महत्वपूर्ण बिट्स लेता है, यदि शेष बिट्स में से कोई भी सेट होता है तो एक जोड़ता है, और उस परिणाम को मिनरुन के रूप में उपयोग करता है। यह एल्गोरिदम सभी सरणियों के लिए काम करता है, जिनमें 64 से छोटी सरणियाँ भी शामिल हैं; 63 या उससे कम आकार की सरणियों के लिए, यह मिनरुन को सरणी आकार के बराबर सेट करता है और टिमसॉर्ट एक सम्मिलन सॉर्ट में कम हो जाता है।^[11]

विश्लेषण

सबसे अच्छे, सबसे खराब और औसत मामले में, टिमसॉर्ट लेता है $O(n\log n)$ किसी सरणी को क्रमबद्ध करने के लिए तुलनाएँ $n$ तत्व. सबसे अच्छे मामले में, जो तब होता है जब इनपुट पहले से ही सॉर्ट किया गया हो, यह रैखिक समय में चलता है, जिसका अर्थ है कि यह एक अनुकूली सॉर्टिंग एल्गोरिदम है।^[3]

ऑब्जेक्ट संदर्भों या पॉइंटर्स को सॉर्ट करने के लिए यह जल्दी से सुलझाएं से बेहतर है क्योंकि इन्हें डेटा तक पहुंचने और तुलना करने के लिए महंगी मेमोरी इनडायरेक्शन की आवश्यकता होती है और क्विकॉर्ट के कैश सुसंगतता लाभ बहुत कम हो जाते हैं।

औपचारिक सत्यापन

2015 में, EU FP7 ENVISAGE प्रोजेक्ट में डच और जर्मन शोधकर्ताओं ने टिमसॉर्ट के मानक कार्यान्वयन में एक बग पाया।^[14] इसे 2015 में Python, Java और Android में ठीक किया गया था।

विशेष रूप से, स्टैक्ड रन आकारों पर अपरिवर्तनीय आवश्यक स्टैक के अधिकतम आकार पर एक तंग ऊपरी सीमा सुनिश्चित करते हैं। कार्यान्वयन ने सॉर्ट 2 के लिए पर्याप्त स्टैक पूर्व-आवंटित किया^{इनपुट के 64 बाइट्स, और आगे अतिप्रवाह जांच से बचा गया।}

हालाँकि, गारंटी के लिए इनवेरिएंट्स को लगातार तीन रनों के प्रत्येक समूह पर लागू करने की आवश्यकता होती है, लेकिन कार्यान्वयन ने इसे केवल शीर्ष तीन के लिए जांचा।^[14] जावा सॉफ़्टवेयर चाबी औपचारिक सत्यापन के लिए KeY टूल का उपयोग करते हुए, शोधकर्ताओं ने पाया कि यह जाँच पर्याप्त नहीं है, और वे रन लंबाई (और इनपुट जो उन रन लंबाई उत्पन्न करते हैं) को खोजने में सक्षम थे, जिसके परिणामस्वरूप स्टैक में गहराई से इनवेरिएंट का उल्लंघन हो सकता था। स्टैक के शीर्ष को मर्ज करने के बाद।^[15] परिणामस्वरूप, कुछ इनपुट के लिए आवंटित आकार सभी असंबद्ध रन को रखने के लिए पर्याप्त नहीं है। जावा में, यह उन इनपुटों के लिए एक ऐरे-आउट-ऑफ-बाउंड अपवाद उत्पन्न करता है। जावा और एंड्रॉइड v7 में इस अपवाद को ट्रिगर करने वाला सबसे छोटा इनपुट आकार का है 67108864 (2²⁶). (पुराने एंड्रॉइड संस्करणों ने पहले ही आकार के कुछ इनपुट के लिए इस अपवाद को ट्रिगर कर दिया है 65536 (2¹⁶))

अद्यतन सबसे खराब स्थिति विश्लेषण के आधार पर पूर्व-आवंटित स्टैक के आकार को बढ़ाकर जावा कार्यान्वयन को ठीक किया गया था। लेख में औपचारिक तरीकों से यह भी दिखाया गया है कि स्टैक में चार सबसे ऊपरी रन ऊपर दिए गए दो नियमों को पूरा करते हैं या नहीं, इसकी जांच करके इच्छित अपरिवर्तनीय को कैसे स्थापित किया जाए। यह दृष्टिकोण Python द्वारा अपनाया गया था^[16] और एंड्रॉइड।

संदर्भ

↑ Peters, Tim (20 July 2002). "[Python-Dev] Sorting". Python Developers Mailinglist. Retrieved 24 February 2011. [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best).
↑ Auger, Nicolas; Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). [DROPS]. doi:10.4230/LIPIcs.ESA.2018.4. ISBN 9783959770811. S2CID 44091254. Retrieved 1 September 2018. TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.
↑ ^3.0 ^3.1 Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.
↑ "[#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort". JDK Bug System. Retrieved 11 June 2014.
↑ "Class: java.util.TimSort<T>". Android Gingerbread Documentation. Archived from the original on 16 July 2015. Retrieved 24 February 2011.
↑ "liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Retrieved 18 February 2013. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.
↑ "Getting things sorted in V8 · V8". v8.dev. Retrieved 21 December 2018.
↑ "Is sort() stable in Swift 5?". Swift Forums (in English). 4 July 2019. Retrieved 4 July 2019.
↑ "टुकड़ा - जंग". doc.rust-lang.org. Retrieved 8 December 2022. The current algorithm is an adaptive, iterative merge sort inspired by timsort. It is designed to be very fast in cases where the slice is nearly sorted, or consists of two or more sorted sequences concatenated one after another.
↑ McIlroy, Peter (January 1993). "Optimistic Sorting and Information Theoretic Complexity". असतत एल्गोरिदम पर चौथे वार्षिक ACM-SIAM संगोष्ठी की कार्यवाही. pp. 467–474. ISBN 0-89871-313-7.
↑ ^11.0 ^11.1 ^11.2 "listsort.txt". Python source code. 18 May 2022. Archived from the original on 28 January 2016.
↑ MacIver, David R. (11 January 2010). "Understanding timsort, Part 1: Adaptive Mergesort". Retrieved 5 December 2015.
↑ Peters, Tim. "listsort.txt". CPython git repository. Retrieved 5 December 2019.
↑ ^14.0 ^14.1 de Gouw, Stijn; Rot, Jurriaan; de Boer, Frank S.; Bubel, Richard; Hähnle, Reiner (July 2015). "OpenJDK's Java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case" (PDF). Computer Aided Verification. Lecture Notes in Computer Science. 9206: 273–289. doi:10.1007/978-3-319-21690-4_16. ISBN 978-3-319-21689-8.
↑ de Gouw, Stijn (24 February 2015). "साबित करना कि एंड्रॉइड, जावा और पायथन का सॉर्टिंग एल्गोरिदम टूटा हुआ है (और इसे ठीक करने का तरीका दिखाएं)". Retrieved 6 May 2017.
↑ Python Issue Tracker – Issue 23515: Bad logic in timsort's merge_collapse

अग्रिम पठन

Auger, Nicolas; Nicaud, Cyril; Pivoteau, Carine (2015). "Merge Strategies: from Merge Sort to TimSort". hal-01212839.
Auger, Jugé, Nicaud, Pivoteau (2018). "On the Worst-Case Complexity of TimSort". ESA 2018.
Sam Buss, Alexander Knop. "Strategies for Stable Merge Sorting." SODA 2019.

बाहरी संबंध

timsort.txt – original explanation by Tim Peters

[1] Peters, Tim (20 July 2002). "[Python-Dev] Sorting". Python Developers Mailinglist. Retrieved 24 February 2011. [Timsort] also has good aspects: It's stable (items that compare equal retain their relative order, so, e.g., if you sort first on zip code, and a second time on name, people with the same name still appear in order of increasing zip code; this is important in apps that, e.g., refine the results of queries based on user input). ... It has no bad cases (O(N log N) is worst case; N−1 compares is best).

[2] Auger, Nicolas; Jugé, Vincent; Nicaud, Cyril; Pivoteau, Carine (2018). [DROPS]. doi:10.4230/LIPIcs.ESA.2018.4. ISBN 9783959770811. S2CID 44091254. Retrieved 1 September 2018. TimSort is an intriguing sorting algorithm designed in 2002 for Python, whose worst-case complexity was announced, but not proved until our recent preprint.

[Chandramouli-3] 3.0 ^3.1 Chandramouli, Badrish; Goldstein, Jonathan (2014). Patience is a Virtue: Revisiting Merge and Sort on Modern Processors. SIGMOD/PODS.

[4] "[#JDK-6804124] (coll) Replace "modified mergesort" in java.util.Arrays.sort with timsort". JDK Bug System. Retrieved 11 June 2014.

[5] "Class: java.util.TimSort<T>". Android Gingerbread Documentation. Archived from the original on 16 July 2015. Retrieved 24 February 2011.

[6] "liboctave/util/oct-sort.cc". Mercurial repository of Octave source code. Lines 23-25 of the initial comment block. Retrieved 18 February 2013. Code stolen in large part from Python's, listobject.c, which itself had no license header. However, thanks to Tim Peters for the parts of the code I ripped-off.

[7] "Getting things sorted in V8 · V8". v8.dev. Retrieved 21 December 2018.

[8] "Is sort() stable in Swift 5?". Swift Forums (in English). 4 July 2019. Retrieved 4 July 2019.

[9] "टुकड़ा - जंग". doc.rust-lang.org. Retrieved 8 December 2022. The current algorithm is an adaptive, iterative merge sort inspired by timsort. It is designed to be very fast in cases where the slice is nearly sorted, or consists of two or more sorted sequences concatenated one after another.

[10] McIlroy, Peter (January 1993). "Optimistic Sorting and Information Theoretic Complexity". असतत एल्गोरिदम पर चौथे वार्षिक ACM-SIAM संगोष्ठी की कार्यवाही. pp. 467–474. ISBN 0-89871-313-7.

[python_timsort-11] 11.0 ^11.1 ^11.2 "listsort.txt". Python source code. 18 May 2022. Archived from the original on 28 January 2016.

[drmaciver-12] MacIver, David R. (11 January 2010). "Understanding timsort, Part 1: Adaptive Mergesort". Retrieved 5 December 2015.

[13] Peters, Tim. "listsort.txt". CPython git repository. Retrieved 5 December 2019.

[broken-14] 14.0 ^14.1 de Gouw, Stijn; Rot, Jurriaan; de Boer, Frank S.; Bubel, Richard; Hähnle, Reiner (July 2015). "OpenJDK's Java.utils.Collection.sort() Is Broken: The Good, the Bad and the Worst Case" (PDF). Computer Aided Verification. Lecture Notes in Computer Science. 9206: 273–289. doi:10.1007/978-3-319-21690-4_16. ISBN 978-3-319-21689-8.

[15] Gouw, Stijn (24 February 2015). "साबित करना कि एंड्रॉइड, जावा और पायथन का सॉर्टिंग एल्गोरिदम टूटा हुआ है (और इसे ठीक करने का तरीका दिखाएं)". Retrieved 6 May 2017.

[16] Python Issue Tracker – Issue 23515: Bad logic in timsort's merge_collapse

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 12: / Line 12: @@
 |optimal=Yes
 }}
-'''टिमसॉर्ट''' एक [[हाइब्रिड एल्गोरिदम|हाइब्रिड]], स्थिर सॉर्टिंग एल्गोरिदम है, जो [[ मर्ज़ सॉर्ट |मर्ज सॉर्ट]] और इंसर्शन सॉर्ट से प्राप्त होता है, जिसे कई प्रकार के वास्तविक दुनिया के डेटा पर अच्छा प्रदर्शन करने के लिए डिज़ाइन किया गया है। इसे [[टिम पीटर्स (सॉफ्टवेयर इंजीनियर)|टिम पीटर्स]] द्वारा 2002 में [[पायथन (प्रोग्रामिंग भाषा)|पायथन]] प्रोग्रामिंग भाषा में उपयोग के लिए लागू किया गया था। एल्गोरिथम पहले से ऑर्डर किए गए डेटा के अनुक्रमों को ढूंढता है (चलता है) और शेष को अधिक कुशलता से क्रमबद्ध करने के लिए उनका उपयोग करता है। यह कुछ मानदंडों को पूरा होने तक रनों को मर्ज करके किया जाता है। संस्करण 2.3 से टिम्सोर्ट पायथन का मानक सॉर्टिंग एल्गोरिदम रहा है।<ref>{{cite web
+'''टिमसॉर्ट''' एक [[हाइब्रिड एल्गोरिदम|हाइब्रिड]], स्थिर सॉर्टिंग एल्गोरिदम है, जो [[ मर्ज़ सॉर्ट |मर्ज सॉर्ट]] और इंसर्शन सॉर्ट से प्राप्त होता है, जिसे कई प्रकार के वास्तविक दुनिया के डेटा पर अच्छा प्रदर्शन करने के लिए डिज़ाइन किया गया है। इसे [[टिम पीटर्स (सॉफ्टवेयर इंजीनियर)|टिम पीटर्स]] द्वारा 2002 में [[पायथन (प्रोग्रामिंग भाषा)|पायथन]] प्रोग्रामिंग भाषा में उपयोग के लिए लागू किया गया था। एल्गोरिथम पहले से ऑर्डर किए गए डेटा के अनुक्रमों को ढूंढता है (चलता है) और शेष को अधिक कुशलता से क्रमबद्ध करने के लिए उनका उपयोग करता है। यह कुछ मानदंडों को पूरा होने तक रनों को मर्ज (संयोजित) करके किया जाता है। संस्करण 2.3 से टिम्सोर्ट पायथन का मानक सॉर्टिंग एल्गोरिदम रहा है।<ref>{{cite web
   | title = [#JDK-6804124] (coll) Replace &quot;modified mergesort&quot; in java.util.Arrays.sort with timsort
   | url = https://bugs.openjdk.java.net/browse/JDK-6804124
@@ Line 37: / Line 37: @@
 यह पीटर मैकिलरॉय के 1993 के पेपर "ऑप्टिमिस्टिक सॉर्टिंग एंड इंफॉर्मेशन थियोरेटिक कॉम्प्लेक्सिटी" की तकनीकों का उपयोग करता है।<ref>{{cite book |contribution=Optimistic Sorting and Information Theoretic Complexity |first=Peter |last=McIlroy |title=असतत एल्गोरिदम पर चौथे वार्षिक ACM-SIAM संगोष्ठी की कार्यवाही| url=https://dl.acm.org/doi/10.5555/313559.313859 |pages=467–474 |date=January 1993 |isbn=0-89871-313-7 }}</ref>
-== ऑपरेशन ==
+== संक्रिया ==
-टिमसॉर्ट को लगातार ऑर्डर किए गए तत्वों के रन का लाभ उठाने के लिए डिज़ाइन किया गया था जो पहले से ही अधिकांश वास्तविक दुनिया डेटा, प्राकृतिक रन में मौजूद हैं। यह डेटा एकत्रित करने वाले तत्वों को रनों में पुनरावृत्त करता है और साथ ही उन रनों को एक स्टैक में रखता है। जब भी स्टैक के शीर्ष पर रन टिमसॉर्ट#मर्ज मानदंड से मेल खाते हैं, तो उन्हें मर्ज कर दिया जाता है। यह तब तक चलता रहता है जब तक कि सभी डेटा का पता नहीं लगा लिया जाता; फिर, सभी रन को एक समय में दो में मिला दिया जाता है और केवल एक क्रमबद्ध रन बचता है। निश्चित आकार की उप-सूचियों को मर्ज करने के बजाय ऑर्डर किए गए रन को मर्ज करने का लाभ यह है कि यह पूरी सूची को सॉर्ट करने के लिए आवश्यक तुलनाओं की कुल संख्या को कम कर देता है।
+टिमसॉर्ट को लगातार क्रम किए गए तत्वों के ''रन'' का लाभ उठाने के लिए डिज़ाइन किया गया था जो पहले से ही अधिकांश वास्तविक दुनिया के डेटा, प्राकृतिक रन में मौजूद हैं। यह डेटा एकत्र करने वाले तत्वों को रन में पुनरावृत्त करता है और साथ ही उन रन को स्टैक में रखता है। जब भी स्टैक के शीर्ष पर रन मर्ज मानदंड से मेल खाते हैं, तो वे मर्ज हो जाते हैं। यह तब तक चलता रहता है जब तक सभी डेटा का पता नहीं लगा लिया जाता है; फिर, सभी रन एक समय में दो रन में विलय हो जाते हैं और केवल एक क्रमबद्ध रन बचता है। निश्चित आकार की उप-सूचियों को मर्ज करने के बजाय ऑर्डर किए गए रन को मर्ज करने का लाभ यह है कि यह पूरी सूची को क्रमबद्ध करने के लिए आवश्यक तुलनाओं की कुल संख्या को कम कर देता है।
-प्रत्येक रन का एक न्यूनतम आकार होता है, जो इनपुट के आकार पर आधारित होता है और एल्गोरिदम की शुरुआत में परिभाषित किया जाता है। यदि कोई रन इस न्यूनतम रन आकार से छोटा है, तो न्यूनतम रन आकार तक पहुंचने तक रन में अधिक तत्व जोड़ने के लिए सम्मिलन सॉर्ट का उपयोग किया जाता है।
+प्रत्येक रन का एक न्यूनतम आकार होता है, जो इनपुट के आकार पर आधारित होता है और एल्गोरिथम की शुरुआत में परिभाषित होता है। यदि कोई रन इस न्यूनतम रन आकार से छोटा है, तो न्यूनतम रन आकार तक पहुंचने तक रन में अधिक तत्व जोड़ने के लिए प्रविष्टि सॉर्ट का उपयोग किया जाता है।
 === मर्ज मानदंड ===
-[[File:Representation of stack for merge memory in Timsort.svg|280px|thumb|रन को [[स्टैक (डेटा संरचना)]] में डाला जाता है। अगर {{nowrap|{{abs|''Z''}} ≤ {{abs|''Y''}} + {{abs|''X''}}}}, फिर X और Y को मर्ज कर दिया जाता है और स्टैक पर प्रतिस्थापित कर दिया जाता है। इस प्रकार, विलय तब तक जारी रहता है जब तक कि सभी रन संतुष्ट न हो जाएं {{nowrap|i. {{abs|''Z''}} > {{abs|''Y''}} + {{abs|''X''}}}} और {{nowrap|ii. {{abs|''Y''}} > {{abs|''X''}}}}.]]टिमसॉर्ट एक स्थिर सॉर्टिंग एल्गोरिदम है (समान कुंजी वाले तत्वों का क्रम रखा जाता है) और संतुलित मर्ज करने का प्रयास करता है (एक मर्ज इस प्रकार समान आकार के रन को मर्ज करता है)।
+[[File:Representation of stack for merge memory in Timsort.svg|280px|thumb|रन को [[स्टैक (डेटा संरचना)]] में डाला जाता है। अगर {{nowrap|{{abs|''Z''}} ≤ {{abs|''Y''}} + {{abs|''X''}}}}, फिर X और Y को मर्ज कर दिया जाता है और स्टैक पर प्रतिस्थापित कर दिया जाता है। इस प्रकार, विलय तब तक जारी रहता है जब तक कि सभी रन संतुष्ट न हो जाएं {{nowrap|i. {{abs|''Z''}} > {{abs|''Y''}} + {{abs|''X''}}}} और {{nowrap|ii. {{abs|''Y''}} > {{abs|''X''}}}}.]]टिमसॉर्ट एक स्थिर सॉर्टिंग एल्गोरिदम है (समान कुंजी वाले तत्वों का क्रम रखा जाता है) और संतुलित मर्ज करने का प्रयास करता है (इस प्रकार एक मर्ज समान आकार के रन को मर्ज करता है)।
-सॉर्टिंग स्थिरता प्राप्त करने के लिए, केवल लगातार रन को मर्ज किया जाता है। दो गैर-लगातार रन के बीच, रन के अंदर एक ही कुंजी वाला एक तत्व हो सकता है। उन दो रनों को मर्ज करने से समान कुंजियों का क्रम बदल जाएगा। इस स्थिति का उदाहरण ([] क्रमबद्ध रन हैं): [1 2 2] 1 4 2 [0 1 2]
+सॉर्टिंग स्थिरता प्राप्त करने के लिए, केवल लगातार रन मर्ज किए जाते हैं। दो गैर-क्रमिक रन के बीच, रन के अंदर एक ही कुंजी वाला एक तत्व हो सकता है। उन दो रन को मिलाने से समान कुंजियों का क्रम बदल जाएगा। इस स्थिति का उदाहरण ([] रन क्रमबद्ध हैं): [1 2 2] 1 4 2 [0 1 2]
-संतुलित मर्ज की खोज में, टिमसॉर्ट स्टैक के शीर्ष पर तीन रन, एक्स, वाई, जेड पर विचार करता है, और इनवेरिएंट को बनाए रखता है:
+एक संतुलित मर्ज की खोज में, टाइमसॉर्ट स्टैक के शीर्ष पर तीन रन, ''X'', ''Y'', ''Z'' पर विचार करता है, और अपरिवर्तनीय को संरक्षित करता है:{{ordered list
-{{ordered list
   | list_style_type=lower-roman
   | {{abs|''Z''}} > {{abs|''Y''}} + {{abs|''X''}}
@@ Line 56: / Line 55: @@
 }}
-यदि इनमें से किसी भी अपरिवर्तनीय का उल्लंघन किया जाता है, तो Y को X या Z में से छोटे के साथ विलय कर दिया जाता है और अपरिवर्तनीयों की फिर से जाँच की जाती है। एक बार जब अपरिवर्तनीय पकड़ में आ जाते हैं, तो डेटा में एक नए रन की खोज शुरू हो सकती है।<ref name=drmaciver>{{cite web |last=MacIver |first=David R. |title=Understanding timsort, Part 1: Adaptive Mergesort |url=http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/ |date=11 January 2010 |access-date=2015-12-05}}</ref> संतुलन के लिए विलय में देरी, [[सीपीयू कैश]] में रन की ताजा घटना का फायदा उठाने और मर्ज निर्णयों को अपेक्षाकृत सरल बनाने के बीच समझौता बनाए रखते हुए ये अपरिवर्तनीय मर्ज को लगभग संतुलित बनाए रखते हैं।
+यदि इनमें से किसी भी अपरिवर्तनीय का उल्लंघन किया जाता है, तो ''Y'' को ''X'' या ''Z'' में से छोटे के साथ विलय कर दिया जाता है और अपरिवर्तनीयों की दोबारा जाँच की जाती है। एक बार जब अपरिवर्तनीय पकड़ में आ जाते हैं, तो डेटा में एक नए रन की खोज शुरू हो सकती है।<ref name=drmaciver>{{cite web |last=MacIver |first=David R. |title=Understanding timsort, Part 1: Adaptive Mergesort |url=http://www.drmaciver.com/2010/01/understanding-timsort-1adaptive-mergesort/ |date=11 January 2010 |access-date=2015-12-05}}</ref> संतुलन के लिए विलय में देरी, [[सीपीयू कैश|कैश]] मेमोरी में रनों की ताज़ा घटना का फायदा उठाने और मर्ज निर्णयों को अपेक्षाकृत सरल बनाने के बीच समझौता बनाए रखते हुए ये अपरिवर्तनीय मर्ज को लगभग संतुलित बनाए रखते हैं।
-=== ओवरहेड स्थान मर्ज करें ===
+=== मर्ज स्पेस ओवरहेड ===
-[[File:Merging procedure for timsort.svg|280px|thumb|मर्ज करने के लिए, टिमसॉर्ट छोटे ऐरे (इस चित्रण में X) के तत्वों को अस्थायी मेमोरी में कॉपी करता है, फिर तत्वों को अंतिम क्रम में X और Y के संयुक्त स्थान में सॉर्ट और भरता है।]]मूल मर्ज सॉर्ट कार्यान्वयन यथास्थान नहीं है और इसमें N (डेटा आकार) का एक स्थान ओवरहेड है। इन-प्लेस मर्ज सॉर्ट कार्यान्वयन मौजूद हैं, लेकिन इसमें बहुत अधिक समय लगता है। एक मध्य अवधि प्राप्त करने के लिए, टिमसॉर्ट एन की तुलना में छोटे समय ओवरहेड और छोटे स्थान ओवरहेड के साथ एक मर्ज सॉर्ट करता है।
+[[File:Merging procedure for timsort.svg|280px|thumb|मर्ज करने के लिए, टिमसॉर्ट छोटे ऐरे (इस चित्रण में X) के तत्वों को अस्थायी मेमोरी में कॉपी करता है, फिर तत्वों को अंतिम क्रम में X और Y के संयुक्त स्थान में सॉर्ट और भरता है।]]मूल मर्ज सॉर्ट कार्यान्वयन यथास्थान नहीं है और इसमें N (डेटा आकार) का एक अतिरिक्त स्थान है। इन-प्लेस मर्ज सॉर्ट कार्यान्वयन मौजूद हैं, लेकिन इसमें काफी समय लगता है। एक मध्य अवधि प्राप्त करने के लिए, टिमसॉर्ट एन की तुलना में छोटे समय ओवरहेड और छोटे स्थान ओवरहेड के साथ मर्ज सॉर्ट करता है।
-सबसे पहले, टिमसॉर्ट उस स्थान को खोजने के लिए एक बाइनरी खोज करता है जहां दूसरे रन का पहला तत्व पहले ऑर्डर किए गए रन में डाला जाएगा, इसे क्रम में रखते हुए। फिर, यह उस स्थान को खोजने के लिए उसी एल्गोरिदम को निष्पादित करता है जहां पहले रन के अंतिम तत्व को दूसरे ऑर्डर किए गए रन में डाला जाएगा, इसे क्रम में रखते हुए। इन स्थानों से पहले और बाद के तत्व पहले से ही अपने सही स्थान पर हैं और उन्हें विलय करने की आवश्यकता नहीं है। फिर, दो रन के शेष तत्वों में से छोटे को अस्थायी मेमोरी में कॉपी किया जाता है, और तत्वों को बड़े रन के साथ अब खाली स्थान में विलय कर दिया जाता है। यदि पहला रन छोटा है, तो मर्ज शुरुआत में शुरू होता है; यदि दूसरा छोटा है, तो मर्ज अंत में शुरू होता है। यह अनुकूलन सामान्य मामले में आवश्यक तत्व आंदोलनों की संख्या, चलने का समय और अस्थायी स्थान को कम कर देता है।
+सबसे पहले, टिमसॉर्ट उस स्थान को ढूंढने के लिए एक बाइनरी खोज करता है जहां दूसरे रन का पहला तत्व पहले ऑर्डर किए गए रन में डाला जाएगा, इसे क्रम में रखते हुए। फिर, यह उस स्थान को ढूंढने के लिए उसी एल्गोरिदम को निष्पादित करता है जहां पहले रन का अंतिम तत्व दूसरे ऑर्डर किए गए रन में डाला जाएगा, इसे क्रम में रखते हुए। इन स्थानों के पहले और बाद के तत्व पहले से ही अपने सही स्थान पर हैं और उन्हें विलय की आवश्यकता नहीं है। फिर, दो रन के शेष तत्वों में से छोटे को अस्थायी मेमोरी में कॉपी किया जाता है, और तत्वों को अब खाली स्थान में बड़े रन के साथ विलय कर दिया जाता है। यदि पहला रन छोटा है, तो मर्ज शुरुआत में ही प्रारंभ हो जाता है; यदि दूसरा छोटा है, तो मर्ज अंत में प्रारंभ होता है। यह अनुकूलन सामान्य स्थिति में आवश्यक तत्व आंदोलनों की संख्या, चलने का समय और अस्थायी स्थान ओवरहेड को कम कर देता है।
-उदाहरण: दो रन [1, 2, 3, 6, 10] और [4, 5, 7, 9, 12, 14, 17] को मर्ज किया जाना चाहिए। ध्यान दें कि दोनों रन पहले से ही अलग-अलग क्रमबद्ध हैं। दूसरे रन का सबसे छोटा तत्व 4 है और इसके क्रम को बनाए रखने के लिए इसे पहले रन के चौथे स्थान पर जोड़ना होगा (यह मानते हुए कि रन की पहली स्थिति 1 है)। पहले रन का सबसे बड़ा तत्व 10 है और इसके क्रम को बनाए रखने के लिए इसे दूसरे रन के पांचवें स्थान पर जोड़ना होगा। इसलिए, [1, 2, 3] और [12, 14, 17] पहले से ही अपनी अंतिम स्थिति में हैं और जिन रन में तत्वों की गतिविधियों की आवश्यकता होती है वे हैं [6, 10] और [4, 5, 7, 9]। इस ज्ञान के साथ, हमें केवल 4 के बजाय 2 आकार का एक अस्थायी बफर आवंटित करने की आवश्यकता है।
+उदाहरण: दो रन [1, 2, 3, 6, 10] और [4, 5, 7, 9, 12, 14, 17] को मिलाना होगा। ध्यान दें कि दोनों रन पहले से ही व्यक्तिगत रूप से क्रमबद्ध हैं। दूसरे रन का सबसे छोटा तत्व 4 है और इसके क्रम को संरक्षित करने के लिए इसे पहले रन के चौथे स्थान पर जोड़ना होगा (यह मानते हुए कि रन की पहली स्थिति 1 है)। पहले रन का सबसे बड़ा तत्व 10 है और इसका क्रम बनाए रखने के लिए इसे दूसरे रन के पांचवें स्थान पर जोड़ना होगा। इसलिए, [1, 2, 3] और [12, 14, 17] पहले से ही अपनी अंतिम स्थिति में हैं और वे रन जिनमें तत्वों की गति की आवश्यकता होती है वे हैं [6, 10] और [4, 5, 7, 9]। इस ज्ञान के साथ, हमें केवल 4 के बजाय आकार 2 का अस्थायी बफर आवंटित करने की आवश्यकता है।
-=== विलय की दिशा ===
+=== मर्ज दिशा ===
-विलय दोनों दिशाओं में किया जा सकता है: बाएँ से दाएँ, जैसा कि पारंपरिक मर्जसॉर्ट में होता है, या दाएँ से बाएँ।
+मर्ज दोनों दिशाओं में किया जा सकता है: बाएं से दाएं, पारंपरिक मर्जसॉर्ट की तरह, या दाएं से बाएं।
 === मर्ज के दौरान सरपट दौड़ने वाला मोड ===

v t e Sorting algorithms
Theory	Computational complexity theory Big O notation Total order Lists Inplacement Stability Comparison sort Adaptive sort Sorting network Integer sorting X + Y sorting Transdichotomous model Quantum sort
Exchange sorts	Bubble sort Cocktail shaker sort Odd–even sort Comb sort Gnome sort Proportion extend sort Quicksort Slowsort Stooge sort Bogosort
Selection sorts	Selection sort Heapsort Smoothsort Cartesian tree sort Tournament sort Cycle sort Weak-heap sort
Insertion sorts	Insertion sort Shellsort Splaysort Tree sort Library sort Patience sorting
Merge sorts	Merge sort Cascade merge sort Oscillating merge sort Polyphase merge sort
Distribution sorts	American flag sort Bead sort Bucket sort Burstsort Counting sort Interpolation sort Pigeonhole sort Proxmap sort Radix sort Flashsort
Concurrent sorts	Bitonic sorter Batcher odd–even mergesort Pairwise sorting network Samplesort
Hybrid sorts	Block merge sort Kirkpatrick–Reisch sort Timsort Introsort Spreadsort Merge-insertion sort
Other	Topological sorting Pre-topological order Pancake sorting Spaghetti sort

Anonymous

Search

टिमसॉर्ट: Difference between revisions

Namespaces

More

Page actions

Revision as of 23:28, 16 July 2023

Contents