किसी सरणी के अनुसार सरणी को कैसे क्रमबद्ध करें? - कलन विधि

मान लीजिए ए = {1,2,3,4}, पी = {36,3,97,19}, सॉर्ट कुंजियों के रूप में पी का उपयोग करें। आप {2,4,1,3} प्राप्त कर सकते हैं।

यह एल्गोरिदम के लिए पुस्तक परिचय में एक उदाहरण है। यह कहता है कि यह nlogn में किया जा सकता है।

क्या कोई मुझे इस बारे में कुछ विचार दे सकता है कि यह कैसे हो सकता हैकिया हुआ? मेरा विचार है कि आपको यह पता लगाने के लिए पी में प्रत्येक तत्व का ट्रैक रखने की आवश्यकता है कि यह कहां समाप्त होता है, जैसे पी [1] पी [3] पर समाप्त होता है, फिर ए [1] ए [3] पर समाप्त होता है। क्या कोई इसे करने के लिए मर्ज सॉर्ट या अन्य नलोग सॉर्टिंग का उपयोग कर सकता है?

मैं एल्गोरिदम के लिए नया हूं और इसे थोड़ा डराता हूं :( किसी भी मदद के लिए धन्यवाद।

उत्तर:

मैं तब से यह मुश्किल नहीं देखता हूं जटिलता सॉर्टिंग एल्गोरिदम का आमतौर पर आवश्यक तुलनाओं की संख्या पर मापा जाता है, आपको केवल सरणी में तत्वों की स्थिति को अपडेट करने की आवश्यकता होती है A तत्वों के अनुसार B। आपको सॉर्ट करने के लिए पहले से जरूरी लोगों के अलावा कोई तुलना करने की ज़रूरत नहीं है B इतनी जटिलता वही है।

हर बार जब आप कोई तत्व ले जाते हैं, तो बस इसे दोनों सरणी में ले जाएं और आप कर चुके हैं।

एक इंडेक्स सरणी बनाएं:

i = { 0, 1, 2, 3 }

अब, जब आप सॉर्ट कर रहे हैं p, इंडेक्स सरणी में एक ही बदलाव करें i.

जब आप "कर चुके हैं, तो आपके पास होगा:

i = { 1, 3, 0, 2 }

दो सरणी को छंटनी जितनी देर तक दो गुना लेती हैएक को सॉर्ट करना (और वास्तव में, यदि आप केवल तुलना की गणना कर रहे हैं तो आपको कोई अतिरिक्त तुलना नहीं करना है, केवल डेटा एक के बजाय दो सरणी में बदल जाता है), ताकि यह समग्र प्रकार की बिग-ओ जटिलता को बदल न सके इसलिये O( 2n log n ) = O(n log n).

अब, आप सॉर्ट किए गए निर्माण के लिए उन इंडेक्स का उपयोग कर सकते हैं A क्रमबद्ध इंडेक्स सरणी के माध्यम से बसने और तत्व के तत्व को देखकर रैखिक समय में सरणी A उस सूचकांक पर। यह लेता है O( n ) पहर।

आपके समग्र एल्गोरिदम की रनटाइम जटिलता सबसे खराब है: O( n + 2n log n ) = O( n log n )

बेशक आप इंडेक्स सरणी को पूरी तरह से छोड़ सकते हैं और सरणी का इलाज कर सकते हैं A उसी तरह, इसे साथ में छंटनी p.