क्रमबद्ध सरणी: Difference between revisions

From Vigyanwiki
(Created page with "{{Short description|Array data structure}} {{Infobox data structure |name=Sorted array |type=Array |invented_by=John von Neumann |invented_year=1945 |space_avg=O(n) |space...")
 
No edit summary
 
(8 intermediate revisions by 3 users not shown)
Line 1: Line 1:
{{Short description|Array data structure}}
{{Short description|Array data structure}}
{{Infobox data structure
{{Infobox data structure
|name=Sorted array
|name=क्रमबद्ध सरणी
|type=Array
|type=सरणी
|invented_by=[[John von Neumann]]
|invented_by=[[जॉन वॉन न्यूमैन]]
|invented_year=1945
|invented_year=1945
|space_avg=O(n)
|space_avg=O(n)
Line 15: Line 15:
}}
}}


एक क्रमबद्ध सरणी एक [[सरणी डेटा संरचना]] है जिसमें प्रत्येक तत्व को संख्यात्मक, वर्णानुक्रमिक, या किसी अन्य क्रम में क्रमबद्ध किया [[आंकड़े]] है, और कंप्यूटर मेमोरी में समान दूरी वाले पतों पर रखा जाता है। यह आमतौर पर [[कंप्यूटर विज्ञान]] में स्थिर और गतिशील डेटा संरचनाओं को लागू करने के लिए उपयोग किया जाता है, जिसमें एक ही [[डेटा प्रकार]] वाले कई मान रखने के लिए [[ तालिका देखो ]] होते हैं। एक सरणी को क्रमबद्ध करना डेटा को क्रमबद्ध रूप में व्यवस्थित करने और उन्हें तेजी से पुनर्प्राप्त करने में उपयोगी होता है।
एक क्रमबद्ध सरणी एक [[सरणी डेटा संरचना]] है जिसमें प्रत्येक तत्व को संख्यात्मक, वर्णानुक्रमिक, या किसी अन्य क्रम में क्रमबद्ध [[आंकड़े]] है, और कंप्यूटर स्मृति में समान दूरी वाले पतों पर रखा जाता है। यह सामान्यतः [[कंप्यूटर विज्ञान]] में स्थिर और गतिशील डेटा संरचनाओं को प्रयुक्त करने के लिए उपयोग किया जाता है, जिसमें एक ही [[डेटा प्रकार]] वाले अधिक मान रखने के लिए [[ तालिका देखो |तालिका लुकअप]] होते हैं। सरणी को क्रमबद्ध करना डेटा को क्रमबद्ध रूप में व्यवस्थित करने और उन्हें तेजी से पुनर्प्राप्त करने में उपयोगी होता है।


== तरीके ==
== विधि ==
ऐसी कई जानी-मानी विधियाँ हैं जिनके द्वारा एक सरणी को सॉर्ट किया जा सकता है, जिसमें शामिल हैं, लेकिन इन तक सीमित नहीं हैं: चयन प्रकार, [[बुलबुले की तरह]], [[सम्मिलन सॉर्ट]], [[मर्ज़ सॉर्ट]], [[जल्दी से सुलझाएं]], [[ढेर बनाएं और छांटें]] और [[गिनती की छँटाई]]{{Citation needed|date=November 2011}} इन सॉर्टिंग तकनीकों के साथ अलग-अलग एल्गोरिदम जुड़े हुए हैं, और इसलिए प्रत्येक विधि का उपयोग करने के अलग-अलग फायदे हैं।
ऐसी कई जानी-मानी विधियाँ हैं जिनके द्वारा सरणी को क्रम में किया जा सकता है, जिसमें सम्मिलित हैं, किन्तुइन तक सीमित नहीं हैं: चयन प्रकार, [[बुलबुले की तरह]], [[सम्मिलन सॉर्ट|सम्मिलन क्रम]], [[मर्ज़ सॉर्ट|मर्ज़ क्रम]], [[जल्दी से सुलझाएं]], [[ढेर बनाएं और छांटें]] और [[गिनती की छँटाई|गिनती की]] [[सम्मिलन सॉर्ट|क्रम]] में इन क्रमबद्ध विधि के साथ अलग-अलग कलन विधि जुड़े हुए हैं, और इसलिए प्रत्येक विधि का उपयोग करने के अलग-अलग लाभ हैं।


== सिंहावलोकन ==
== अवलोकन ==
अनुक्रमिक रूप से संग्रहीत डेटा के लिए संदर्भ की सर्वोत्तम स्थानीयता के साथ क्रमबद्ध सरणियाँ सबसे अधिक स्थान-कुशल डेटा संरचना हैं।{{Citation needed|date=November 2011}}
अनुक्रमिक रूप से संग्रहीत डेटा के लिए संदर्भ की सर्वोत्तम स्थानीयता के साथ क्रमबद्ध सरणियाँ सबसे अधिक स्थान-कुशल डेटा संरचना हैं।


एक क्रमबद्ध सरणी के भीतर तत्वों को (लॉग एन) में बाइनरी खोज का उपयोग करके पाया जाता है; इस प्रकार क्रमबद्ध सरणियाँ उन मामलों के लिए अनुकूल होती हैं जब किसी को तत्वों को जल्दी से देखने में सक्षम होने की आवश्यकता होती है, उदा। एक [[सेट (कंप्यूटर विज्ञान)]] या सेट (कंप्यूटर विज्ञान) के रूप में#मल्टीसेट [[डेटा संरचना]]। लुकअप के लिए यह जटिलता [[स्व-संतुलन [[ द्विआधारी खोज ]] ट्री]] के समान है।
एक क्रमबद्ध सरणी के अंदर अवयव को O(log ''n'') में बाइनरी खोज का उपयोग करके पाया जाता है; इस प्रकार क्रमबद्ध सरणियाँ उन स्थितियोंके लिए अनुकूल होती हैं जब किसी को अवयव को जल्दी से देखने में सक्षम होने की आवश्यकता होती है, उदा। [[सेट (कंप्यूटर विज्ञान)|समुच्चय (कंप्यूटर विज्ञान)]] या समुच्चय (कंप्यूटर विज्ञान) के रूप में या बहु समुच्चय [[डेटा संरचना]]। लुकअप के लिए यह जटिलता <nowiki>[[सेल्फ बैलेंसिंग बाइनरी सर्च ट्री]]</nowiki> के समान है।


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


यदि कोई क्रमबद्ध [[गतिशील सरणी]] का उपयोग कर रहा है, तो तत्वों को सम्मिलित करना और हटाना संभव है। एक क्रमबद्ध सरणी में तत्वों का सम्मिलन और विलोपन (एन) पर निष्पादित होता है, तत्व को डालने या हटाए जाने के बाद सभी तत्वों को स्थानांतरित करने की आवश्यकता के कारण; एक स्व-संतुलन बाइनरी सर्च ट्री की तुलना में (लॉग एन) पर आवेषण और हटा देता है। ऐसे मामले में जहां तत्वों को हटा दिया जाता है या अंत में डाला जाता है, एक क्रमबद्ध गतिशील सरणी [[परिशोधित विश्लेषण]] (1) समय में ऐसा कर सकती है जबकि स्व-संतुलन बाइनरी सर्च ट्री हमेशा ओ (लॉग एन) पर काम करता है।
यदि कोई क्रमबद्ध [[गतिशील सरणी]] का उपयोग कर रहा है, तो अवयव को सम्मिलित करना और हटाना संभव है। क्रमबद्ध सरणी में अवयव का सम्मिलन और विलोपन O(''n'') पर निष्पादित होता है, तत्व को डालने या हटाए जाने के बाद सभी अवयव को स्थानांतरित करने की आवश्यकता के कारण; स्व-संतुलन बाइनरी सर्च ट्री की तुलना में O(log ''n'') पर आवेषण और हटा देता है। ऐसे स्थति में जहां अवयव को हटा दिया जाता है या अंत में डाला जाता है, क्रमबद्ध गतिशील सरणी [[परिशोधित विश्लेषण]] O(1) समय में ऐसा कर सकती है जबकि स्व-संतुलन बाइनरी सर्च ट्री सदैव O(log ''n'') पर काम करता है।


क्रमबद्ध सरणी में तत्वों को उनके सूचकांक (यादृच्छिक अभिगम) द्वारा O(1) समय पर देखा जा सकता है, अधिक जटिल डेटा संरचनाओं के लिए O(log n) या O(n) समय लेने वाला एक ऑपरेशन।
क्रमबद्ध सरणी में अवयव को उनके सूचकांक (यादृच्छिक अभिगम) द्वारा O(1) समय पर देखा जा सकता है, अधिक जटिल डेटा संरचनाओं के लिए O(log n) या O(n) समय लेने वाला ऑपरेशन है।


== इतिहास ==
== इतिहास ==
[[जॉन वॉन न्यूमैन]] ने 1945 में पहला एरे सॉर्टिंग प्रोग्राम (मर्ज सॉर्ट) लिखा था, जब [[EDVAC]]|पहला संग्रहित प्रोग्राम कंप्यूटर अभी भी बनाया जा रहा था।<ref>[[Donald Knuth]], ''[[The Art of Computer Programming]]'', vol. 3. Addison-Wesley</ref>
[[जॉन वॉन न्यूमैन]] ने 1945 में पहला सरणी क्रमबद्ध प्रोग्राम (मर्ज क्रम में) लिखा था, जब पहला संग्रहित प्रोग्राम कंप्यूटर अभी भी बनाया जा रहा था।<ref>[[Donald Knuth]], ''[[The Art of Computer Programming]]'', vol. 3. Addison-Wesley</ref>
 


== क्रमबद्ध सरणियों के अनुप्रयोग ==
== क्रमबद्ध सरणियों के अनुप्रयोग ==


=== वाणिज्यिक कंप्यूटिंग<ref>{{cite web | url=http://algs4.cs.princeton.edu/25applications/ | title=Sorting Applications }}</ref>===
=== वाणिज्यिक कंप्यूटिंग<ref>{{cite web | url=http://algs4.cs.princeton.edu/25applications/ | title=Sorting Applications }}</ref>===
सरकारी संगठनों, निजी कंपनियों और कई वेब-आधारित अनुप्रयोगों को भारी मात्रा में डेटा से निपटना पड़ता है। डेटा को अक्सर कई बार एक्सेस करना होगा। डेटा को क्रमबद्ध प्रारूप में रखने से त्वरित और आसान पुनर्प्राप्ति की अनुमति मिलती है।
सरकारी संगठनों, निजी कंपनियों और कई वेब-आधारित अनुप्रयोगों को अधिक मात्रा में डेटा से निपटना पड़ता है। डेटा को अधिकांशतः अधिक बार अभिगम करना होगा। डेटा को क्रमबद्ध प्रारूप में रखने से त्वरित और आसान पुनर्प्राप्ति की अनुमति मिलती है।


=== असतत गणित में ===
=== असतत गणित में ===
दिज्क्स्ट्रा के एल्गोरिथ्म या प्राइम के एल्गोरिथ्म को लागू करने के लिए क्रमबद्ध सरणियों का उपयोग किया जा सकता है। साथ ही, न्यूनतम फैले पेड़ खोजने के लिए क्रुस्कल के एल्गोरिदम जैसे एल्गोरिदम।
दिज्क्स्ट्रा के कलन विधि या प्राइम के कलन विधि को प्रयुक्त करने के लिए क्रमबद्ध सरणियों का उपयोग किया जा सकता है। साथ ही, न्यूनतम सपैनिंग ट्री प्राप्त करने के लिए क्रुस्कल के कलन विधि का उपयोग किया जा सकता है।


=== प्राथमिकता निर्धारण में ===
=== प्राथमिकता निर्धारण में ===
[[ऑपरेटिंग सिस्टम]] स्तर पर, एक समय में कई प्रक्रियाएँ लंबित होती हैं, लेकिन वे एक ही समय में केवल एक ही प्रक्रिया को संभाल सकती हैं। इसलिए, प्राथमिकताएं प्रत्येक प्रक्रिया से जुड़ी होती हैं। फिर प्रक्रिया आईडी के क्रमबद्ध सरणी का उपयोग करके प्रक्रियाओं को सर्वोच्च प्राथमिकता के अनुसार सीपीयू को भेजा जाता है। यहाँ, प्रक्रियाओं को उनकी प्राथमिकताओं के आधार पर क्रमबद्ध किया जाता है और फिर उन्हें CPU आवंटित किया जाता है। उच्चतम प्राथमिकता वाली प्रक्रिया क्रमबद्ध सरणी में प्रथम स्थान लेती है। इसलिए प्राथमिकता-वार सिस्टम प्रोसेस शेड्यूलिंग की जाती है।<ref>{{cite book|title=ऑपरेटिंग सिस्टम की अवधारणा पीटर बी. गैल्विन द्वारा|publisher=WILEY-INDIA Pvt. limited|isbn=978-81-265-2051-0}}</ref>
[[ऑपरेटिंग सिस्टम|ऑपरेटिंग]] प्रणाली स्तर पर, समय में अधिक प्रक्रियाएँ लंबित होती हैं, किन्तु वे ही समय में केवल ही प्रक्रिया को संभाल सकती हैं। इसलिए, प्राथमिकताएं प्रत्येक प्रक्रिया से जुड़ी होती हैं। फिर प्रक्रिया आईडी के क्रमबद्ध सरणी का उपयोग करके प्रक्रियाओं को सर्वोच्च प्राथमिकता के अनुसार सीपीयू को भेजा जाता है। यहाँ, प्रक्रियाओं को उनकी प्राथमिकताओं के आधार पर क्रमबद्ध किया जाता है और फिर उन्हें सीपीयू आवंटित किया जाता है। उच्चतम प्राथमिकता वाली प्रक्रिया क्रमबद्ध सरणी में प्रथम स्थान लेती है। इसलिए प्राथमिकता-वार प्रणाली प्रक्रिया नियोजन की जाती है।<ref>{{cite book|title=ऑपरेटिंग सिस्टम की अवधारणा पीटर बी. गैल्विन द्वारा|publisher=WILEY-INDIA Pvt. limited|isbn=978-81-265-2051-0}}</ref>
 


=== सबसे छोटे-नौकरी-पहले शेड्यूलिंग में ===
=== अल्पतम- कार्य-प्रथम नियोजन में ===
यह प्राथमिकता निर्धारण का विशेष मामला है। यहां, प्रक्रियाओं के फटने के समय के अनुसार प्रक्रियाओं को क्रमबद्ध किया जाता है। कम से कम समय लेने वाली प्रक्रिया को पहले सीपीयू आवंटित किया जाएगा। इसलिए, प्रक्रियाओं को उनके बर्स्ट टाइम के अनुसार सीपीयू में भेजा जा रहा है।
यह प्राथमिकता निर्धारण का विशेष स्तथिति है। यहां, प्रक्रियाओं के बर्स्ट के समय के अनुसार प्रक्रियाओं को क्रमबद्ध किया जाता है। कम से कम समय लेने वाली प्रक्रिया को पहले सीपीयू आवंटित किया जाएगा। इसलिए, प्रक्रियाओं को उनके बर्स्ट टाइम के अनुसार सीपीयू में भेजा जा रहा है।
फ़ाइल:प्राथमिकता निर्धारण.पीडीएफ|सही
{| class="wikitable"
{| class="wikitable"
|-
|-
! Process !! Burst time
! प्रक्रिया !! बर्स्ट टाइम
|-
|-
| P1 ||  3
| P1 ||  3
Line 67: Line 64:


== यह भी देखें ==
== यह भी देखें ==
* [[छँटाई एल्गोरिथ्म]]
* [[छँटाई एल्गोरिथ्म|क्रमबद्ध कलन विधि]]
* [[बाइनरी सर्च एल्गोरिथम]]
* [[बाइनरी सर्च एल्गोरिथम|बाइनरी सर्च कलन विधि]]
* [[ढेर (डेटा संरचना)]]
* [[ढेर (डेटा संरचना)]]
* [[डेटा संरचना खोजें]]
* [[डेटा संरचना खोजें]]
Line 74: Line 71:
==संदर्भ==
==संदर्भ==
{{reflist|2}}
{{reflist|2}}
[[Category: सरणियों]]


[[Category: Machine Translated Page]]
[[Category:Created On 24/02/2023]]
[[Category:Created On 24/02/2023]]
[[Category:Lua-based templates]]
[[Category:Machine Translated Page]]
[[Category:Pages with script errors]]
[[Category:Short description with empty Wikidata description]]
[[Category:Templates Vigyan Ready]]
[[Category:Templates that add a tracking category]]
[[Category:Templates that generate short descriptions]]
[[Category:Templates using TemplateData]]
[[Category:सरणियों]]

Latest revision as of 15:50, 16 March 2023

क्रमबद्ध सरणी
Typeसरणी
Invented1945
Invented byजॉन वॉन न्यूमैन
Time complexity in big O notation
Algorithm Average Worst case
Space O(n) O(n)
Search O(log n) O(log n)
Insert O(n) O(n)
Delete O(n) O(n)

एक क्रमबद्ध सरणी एक सरणी डेटा संरचना है जिसमें प्रत्येक तत्व को संख्यात्मक, वर्णानुक्रमिक, या किसी अन्य क्रम में क्रमबद्ध आंकड़े है, और कंप्यूटर स्मृति में समान दूरी वाले पतों पर रखा जाता है। यह सामान्यतः कंप्यूटर विज्ञान में स्थिर और गतिशील डेटा संरचनाओं को प्रयुक्त करने के लिए उपयोग किया जाता है, जिसमें एक ही डेटा प्रकार वाले अधिक मान रखने के लिए तालिका लुकअप होते हैं। सरणी को क्रमबद्ध करना डेटा को क्रमबद्ध रूप में व्यवस्थित करने और उन्हें तेजी से पुनर्प्राप्त करने में उपयोगी होता है।

विधि

ऐसी कई जानी-मानी विधियाँ हैं जिनके द्वारा सरणी को क्रम में किया जा सकता है, जिसमें सम्मिलित हैं, किन्तुइन तक सीमित नहीं हैं: चयन प्रकार, बुलबुले की तरह, सम्मिलन क्रम, मर्ज़ क्रम, जल्दी से सुलझाएं, ढेर बनाएं और छांटें और गिनती की क्रम में इन क्रमबद्ध विधि के साथ अलग-अलग कलन विधि जुड़े हुए हैं, और इसलिए प्रत्येक विधि का उपयोग करने के अलग-अलग लाभ हैं।

अवलोकन

अनुक्रमिक रूप से संग्रहीत डेटा के लिए संदर्भ की सर्वोत्तम स्थानीयता के साथ क्रमबद्ध सरणियाँ सबसे अधिक स्थान-कुशल डेटा संरचना हैं।

एक क्रमबद्ध सरणी के अंदर अवयव को O(log n) में बाइनरी खोज का उपयोग करके पाया जाता है; इस प्रकार क्रमबद्ध सरणियाँ उन स्थितियोंके लिए अनुकूल होती हैं जब किसी को अवयव को जल्दी से देखने में सक्षम होने की आवश्यकता होती है, उदा। समुच्चय (कंप्यूटर विज्ञान) या समुच्चय (कंप्यूटर विज्ञान) के रूप में या बहु समुच्चय डेटा संरचना। लुकअप के लिए यह जटिलता [[सेल्फ बैलेंसिंग बाइनरी सर्च ट्री]] के समान है।

कुछ डेटा संरचनाओं में, संरचनाओं की सरणी का उपयोग किया जाता है। ऐसे स्थितियोंमें, संरचना तत्व के रूप में कुछ कुंजी के अनुसार संरचनाओं को क्रम में करने के लिए समान क्रमबद्ध विधियों का उपयोग किया जा सकता है; उदाहरण के लिए, रोल नंबर या नाम या श्रेणी के अनुसार छात्रों के आंकन को छांटना के लिए ।

यदि कोई क्रमबद्ध गतिशील सरणी का उपयोग कर रहा है, तो अवयव को सम्मिलित करना और हटाना संभव है। क्रमबद्ध सरणी में अवयव का सम्मिलन और विलोपन O(n) पर निष्पादित होता है, तत्व को डालने या हटाए जाने के बाद सभी अवयव को स्थानांतरित करने की आवश्यकता के कारण; स्व-संतुलन बाइनरी सर्च ट्री की तुलना में O(log n) पर आवेषण और हटा देता है। ऐसे स्थति में जहां अवयव को हटा दिया जाता है या अंत में डाला जाता है, क्रमबद्ध गतिशील सरणी परिशोधित विश्लेषण O(1) समय में ऐसा कर सकती है जबकि स्व-संतुलन बाइनरी सर्च ट्री सदैव O(log n) पर काम करता है।

क्रमबद्ध सरणी में अवयव को उनके सूचकांक (यादृच्छिक अभिगम) द्वारा O(1) समय पर देखा जा सकता है, अधिक जटिल डेटा संरचनाओं के लिए O(log n) या O(n) समय लेने वाला ऑपरेशन है।

इतिहास

जॉन वॉन न्यूमैन ने 1945 में पहला सरणी क्रमबद्ध प्रोग्राम (मर्ज क्रम में) लिखा था, जब पहला संग्रहित प्रोग्राम कंप्यूटर अभी भी बनाया जा रहा था।[1]

क्रमबद्ध सरणियों के अनुप्रयोग

वाणिज्यिक कंप्यूटिंग[2]

सरकारी संगठनों, निजी कंपनियों और कई वेब-आधारित अनुप्रयोगों को अधिक मात्रा में डेटा से निपटना पड़ता है। डेटा को अधिकांशतः अधिक बार अभिगम करना होगा। डेटा को क्रमबद्ध प्रारूप में रखने से त्वरित और आसान पुनर्प्राप्ति की अनुमति मिलती है।

असतत गणित में

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

प्राथमिकता निर्धारण में

ऑपरेटिंग प्रणाली स्तर पर, समय में अधिक प्रक्रियाएँ लंबित होती हैं, किन्तु वे ही समय में केवल ही प्रक्रिया को संभाल सकती हैं। इसलिए, प्राथमिकताएं प्रत्येक प्रक्रिया से जुड़ी होती हैं। फिर प्रक्रिया आईडी के क्रमबद्ध सरणी का उपयोग करके प्रक्रियाओं को सर्वोच्च प्राथमिकता के अनुसार सीपीयू को भेजा जाता है। यहाँ, प्रक्रियाओं को उनकी प्राथमिकताओं के आधार पर क्रमबद्ध किया जाता है और फिर उन्हें सीपीयू आवंटित किया जाता है। उच्चतम प्राथमिकता वाली प्रक्रिया क्रमबद्ध सरणी में प्रथम स्थान लेती है। इसलिए प्राथमिकता-वार प्रणाली प्रक्रिया नियोजन की जाती है।[3]

अल्पतम- कार्य-प्रथम नियोजन में

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

प्रक्रिया बर्स्ट टाइम
P1 3
P2 4
P3 1
P4 8
P5 6


यह भी देखें

संदर्भ

  1. Donald Knuth, The Art of Computer Programming, vol. 3. Addison-Wesley
  2. "Sorting Applications".
  3. ऑपरेटिंग सिस्टम की अवधारणा पीटर बी. गैल्विन द्वारा. WILEY-INDIA Pvt. limited. ISBN 978-81-265-2051-0.