सोलोमन की सॉर्ट

नया साल मंगलमय हो!

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

1 से n तक एन पॉजिटिव पूर्णांकों का एक सेट N होने दें।
यह स्वयं स्पष्ट है कि n संख्याओं को संग्रहीत करने के लिए, आपके पास n कोशिकाएँ होनी चाहिए। चाहे जिस क्रम में नंबर लिखे जाएंगे।

स्रोत सरणी

3

5

2

1

8

4

7

6

9

10

यह कल्पना करना आसान है कि एक अनियंत्रित सेट एन को आसानी से एक ऑर्डर किए गए (आरोही या अवरोही क्रम में) के साथ बदला जा सकता है, एक अनियंत्रित एक के स्थान पर एक ऑर्डर किए गए सेट को लिखना।

आदेश दिया सरणी

1

2

3

4

5

6

7

8

9

10

उसी तरह, संख्याओं के एक "सॉर्ट" कर सकते हैं (हम खुद को सकारात्मक पूर्णांक तक सीमित करते हैं) स्थिति n _{अधिकतम} -n = n को संतुष्ट करते हैं।

अधिक जटिल मामले पर विचार करें।

बता दें कि सेट N (फिर से, पॉजिटिव पूर्णांक) ऐसा है कि n _{अधिकतम} -n _min > n , और सेट में सभी संख्याएँ n (i) भिन्न हैं।

30

55

21

17

82

46

79

63

94

108

इस सेट को क्रमबद्ध करने के लिए, आपको चाहिए:
1) n _{अधिकतम} , n _मि
2) डेल्टा d = (n _{अधिकतम} -n _मिनट ) / n की गणना करें
3) प्रत्येक n (i) के लिए (निम्नलिखित प्रक्रिया को सशर्त रूप से "पत्थरों के बिखरने") कहा जाएगा:
3a) इंडेक्स की गणना करें इंडेक्स = (n (i) -n _मिनट ) / d + 1 (चूंकि गणना भी पूर्णांकों में मानी जाती है, राउंडिंग की क्षतिपूर्ति और शून्य इंडेक्स को समाप्त करने के लिए एक यूनिट जोड़ा जाता है)

संख्या n (i) और indx ind ऐसी जगहें हैं जहां इन नंबरों को खड़ा होना चाहिए।

30	55	21	17	82	46	79	63	94	108
2	5	1	1	7	4	7	5	9	10

3 बी) इंडेक्स के पूर्व-तैयार सरणी में इंडेक्स शून्य से भरा हुआ है, पिछले चरण में प्राप्त सूचकांक के साथ सेल को बढ़ाएं

2

1

0

1

2

0

2

0

1

1

3 सी) परिणामी मूल्य पढ़ें
3 डी) हम इसे n से गुणा करते हैं और इसे इंडेक्स के साथ जोड़ते हैं, इस पते पर सरणी N में नंबर n (i) लिखें
यदि समरूप अनुक्रमणिकाएँ आर-पार आती हैं, तो n (i) सरणी N में _नया नहीं, बल्कि नीचे _से लिखा _जाता है।

21	30		46	55		82		94	108
17				63		79

4) फिर "पत्थरों के संग्रह" के लिए आगे बढ़ें
हम i = 1 डालते हैं और क्रमिक रूप से सूचकांक इंडेक्स की सरणी पढ़ते हैं जबकि मैं = n
4a) यदि Indxs (i) = 0, अगले i पर जाएं
4b) अगर Indxs (i) = 1, सरणी N _नए से संख्या पढ़ें, इसे क्रमबद्ध सरणी में आउटपुट करें, अगले i पर जाएं
4c) यदि Indxs (i) = 2, हम N के _नए अंक "लंबवत" से पढ़ते हैं, उनकी तुलना करें और पहले छोटे को प्रिंट करें, फिर बड़ा, अगले i पर जाएं
4d) यदि Indxs (i) = 3, 3 नंबर पढ़ते हैं, उनमें से न्यूनतम खोजें, इसे प्रिंट करें और इसे सूची से हटा दें, फिर दो शेष लोगों की तुलना करें और उन्हें पहले ही प्रिंट कर लें।
4e) Indxs (i) = 4 के लिए, सब कुछ समान है, पहले चार का न्यूनतम पता लगाएं, इसे पार करें, फिर इंडेक्स 3 के लिए भी ऐसा ही करें।
4e) यदि Indxs (i) 4 से अधिक है, तो हम एल्गोरिदम को पुनरावर्ती कहते हैं।
क्रमबद्ध सरणी

17

21

30

46

55

63

79

82

94

108

चलो संचालन की संख्या का अनुमान लगाने की कोशिश करते हैं।
न्यूनतम और अधिकतम की खोज करने के लिए, आपको एक पास - एन ऑपरेशन की आवश्यकता है।
"बिखरे हुए पत्थर" के लिए एन ऑपरेशन हैं।
लागत के लिए "पत्थरों का संग्रह" इनपुट पर निर्भर करता है। इस मामले में, आपको संख्याओं की एक जोड़ी की तुलना करने के लिए n प्रतियां और 3 संचालन की आवश्यकता है।

जब random.org से प्राप्त n = 10000 के साथ सेट पर परीक्षण किया जाता है (संसाधन एक सेट में 10000 से अधिक नंबर नहीं देता है), एल्गोरिथ्म निम्नलिखित आँकड़े दिखाता है:
N _{अधिकतम} = 10000 के साथ। सभी अनुक्रमणिका = 1, क्रमबद्धता सरणी के माध्यम से 3 पास में होती है।
N _{अधिकतम} = 11000 के साथ। शून्य के लगभग आधे: 4547, 906 की इकाइयाँ, दो: 4547, त्रिगुण और अधिक: 0 वही तीन पास, साथ ही 2 संख्याओं की n तुलनाओं का लगभग आधा।
N _{अधिकतम} = 21000 शून्य के साथ: 3967 पुरुष: 2845 जुड़वां: 2409 पेड़: 779 चौके: 0
N _{अधिकतम} = 31000 शून्य के साथ: 3881 लोग: 3134 Twos: 2197 पेड़: 680 चौके: 108 More_than_four: 0
इंडेक्स में n _{अधिकतम} = 101000 अधिकतम के साथ: 6 जीरो: 3729 ओएनस: 3541 ट्वोस: 1923 पेड़: 643 चौके: 139 More_than_four: 25
दूसरे पुनरावृत्ति के केवल 25 कॉल।

सहज रूप से, सबसे खराब स्थिति में, n / 5 पुनरावृत्तियों का प्रदर्शन किया जाएगा।
औसतन, ऑफहैंड, ऑपरेशन की संख्या 4n के क्रम की है

यह छँटाई विधि तुलना के बिना छँटाई समूह के अंतर्गत आता है और हाथ और गिनती छँटाई के बीच एक मध्यवर्ती संस्करण है।

गिनती के आधार पर छंटनी की मुख्य समस्या इसके अलावा उन मूल्यों को क्रमबद्ध करना है जो एक सेल में आते हैं, यह महत्वपूर्ण है जब सेल में संख्याओं की संख्या 4 से अधिक हो।
लेकिन, सबसे पहले, हमारे पास इकाइयों और संख्याओं के जोड़े के कारण एक अच्छा बाधा है।
दूसरे, फटने की संख्या आमतौर पर अपेक्षाकृत कम होती है, एक प्रतिशत से भी कम।
तीसरा, पहले से ही दूसरे पुनरावृत्ति पर, फटने को बहुत अच्छी तरह से काम किया जाता है। इसके अलावा, इनपुट डेटा में पुनरावृत्ति की अनुपस्थिति पर प्रतिबंध स्वचालित रूप से हटा दिया जाता है। यदि हम समान मूल्यों से एक फट पर आते हैं, तो इसके लिए डेल्टा d = (n _{अधिकतम} -n _मिनट ) / n = 0 है और हम सुरक्षित रूप से पूरे फट को आउटपुट में कॉपी कर सकते हैं।

न केवल सकारात्मक पूर्णांक के लिए इस छँटाई विधि की प्रयोज्यता समस्या भी पूरी तरह से हल है।

बेशक, इस विधि में अधिक विराम और नुकसान की पहचान की आवश्यकता है।

फायदे:
गति, समझने में आसानी और प्रोग्रामिंग।
नुकसान:
इनपुट डेटा के आधार पर, बड़ी मेमोरी आवश्यकताएं। आप एन _नए सरणी के अधिक तर्कसंगत संगठन द्वारा क्षतिपूर्ति करने का प्रयास कर सकते हैं। किसी भी मामले में, स्मृति को कम से कम 3n की आवश्यकता होती है।

युपीडी:
GitHub पर टेस्ट फोर्ट कोड