क्रमबद्ध सरणी: 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
Line 15: Line 15:
}}
}}


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


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


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


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


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


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


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


=== असतत गणित में ===
=== असतत गणित में ===
Line 44: Line 44:


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




Revision as of 20:04, 2 March 2023

Sorted array
TypeArray
Invented1945
Invented byJohn von Neumann
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)

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

तरीके

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

सिंहावलोकन

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

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

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

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

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

इतिहास

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


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

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

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

असतत गणित में

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

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

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


सबसे छोटे-नौकरी-पहले शेड्यूलिंग में

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

Process Burst time
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.
Retrieved from ‘https://www.vigyanwiki.in/index.php?title=क्रमबद्ध_सरणी&oldid=109676’