क्रमबद्ध सरणी: Difference between revisions
No edit summary |
No edit summary |
||
| Line 15: | Line 15: | ||
}} | }} | ||
एक क्रमबद्ध सरणी एक [[सरणी डेटा संरचना]] है जिसमें प्रत्येक तत्व को संख्यात्मक, वर्णानुक्रमिक, या किसी अन्य क्रम में क्रमबद्ध [[आंकड़े]] है, और कंप्यूटर स्मृति में समान दूरी वाले पतों पर रखा जाता है। यह | एक क्रमबद्ध सरणी एक [[सरणी डेटा संरचना]] है जिसमें प्रत्येक तत्व को संख्यात्मक, वर्णानुक्रमिक, या किसी अन्य क्रम में क्रमबद्ध [[आंकड़े]] है, और कंप्यूटर स्मृति में समान दूरी वाले पतों पर रखा जाता है। यह सामान्यतः [[कंप्यूटर विज्ञान]] में स्थिर और गतिशील डेटा संरचनाओं को प्रयुक्त करने के लिए उपयोग किया जाता है, जिसमें एक ही [[डेटा प्रकार]] वाले अधिक मान रखने के लिए [[ तालिका देखो |तालिका लुकअप]] होते हैं। सरणी को क्रमबद्ध करना डेटा को क्रमबद्ध रूप में व्यवस्थित करने और उन्हें तेजी से पुनर्प्राप्त करने में उपयोगी होता है। | ||
== विधि == | == विधि == | ||
ऐसी कई जानी-मानी विधियाँ हैं जिनके द्वारा सरणी को क्रम में | ऐसी कई जानी-मानी विधियाँ हैं जिनके द्वारा सरणी को क्रम में किया जा सकता है, जिसमें सम्मिलित हैं, किन्तुइन तक सीमित नहीं हैं: चयन प्रकार, [[बुलबुले की तरह]], [[सम्मिलन सॉर्ट|सम्मिलन क्रम]], [[मर्ज़ सॉर्ट|मर्ज़ क्रम]], [[जल्दी से सुलझाएं]], [[ढेर बनाएं और छांटें]] और [[गिनती की छँटाई|गिनती की]] [[सम्मिलन सॉर्ट|क्रम]] में इन क्रमबद्ध विधि के साथ अलग-अलग कलन विधि जुड़े हुए हैं, और इसलिए प्रत्येक विधि का उपयोग करने के अलग-अलग लाभ हैं। | ||
== अवलोकन == | == अवलोकन == | ||
अनुक्रमिक रूप से संग्रहीत डेटा के लिए संदर्भ की सर्वोत्तम स्थानीयता के साथ क्रमबद्ध सरणियाँ सबसे अधिक स्थान-कुशल डेटा संरचना हैं। | अनुक्रमिक रूप से संग्रहीत डेटा के लिए संदर्भ की सर्वोत्तम स्थानीयता के साथ क्रमबद्ध सरणियाँ सबसे अधिक स्थान-कुशल डेटा संरचना हैं। | ||
एक क्रमबद्ध सरणी के अंदर अवयव को O(log ''n'') | एक क्रमबद्ध सरणी के अंदर अवयव को O(log ''n'') में बाइनरी खोज का उपयोग करके पाया जाता है; इस प्रकार क्रमबद्ध सरणियाँ उन स्थितियोंके लिए अनुकूल होती हैं जब किसी को अवयव को जल्दी से देखने में सक्षम होने की आवश्यकता होती है, उदा। [[सेट (कंप्यूटर विज्ञान)|समुच्चय (कंप्यूटर विज्ञान)]] या समुच्चय (कंप्यूटर विज्ञान) के रूप में या बहु समुच्चय [[डेटा संरचना]]। लुकअप के लिए यह जटिलता <nowiki>[[सेल्फ बैलेंसिंग बाइनरी सर्च ट्री]]</nowiki> के समान है। | ||
कुछ डेटा संरचनाओं में, संरचनाओं की सरणी का उपयोग किया जाता है। ऐसे स्थितियोंमें, संरचना तत्व के रूप में कुछ कुंजी के अनुसार संरचनाओं को क्रम में करने के लिए समान क्रमबद्ध विधियों का उपयोग किया जा सकता है; उदाहरण के लिए, रोल नंबर या नाम या श्रेणी के अनुसार छात्रों के आंकन को छांटना के लिए । | कुछ डेटा संरचनाओं में, संरचनाओं की सरणी का उपयोग किया जाता है। ऐसे स्थितियोंमें, संरचना तत्व के रूप में कुछ कुंजी के अनुसार संरचनाओं को क्रम में करने के लिए समान क्रमबद्ध विधियों का उपयोग किया जा सकता है; उदाहरण के लिए, रोल नंबर या नाम या श्रेणी के अनुसार छात्रों के आंकन को छांटना के लिए । | ||
यदि कोई क्रमबद्ध [[गतिशील सरणी]] का उपयोग कर रहा है, तो अवयव को सम्मिलित करना और हटाना संभव है। क्रमबद्ध सरणी में अवयव का सम्मिलन और विलोपन O(''n'') पर निष्पादित होता है, तत्व को डालने या हटाए जाने के बाद सभी अवयव को स्थानांतरित करने की आवश्यकता के कारण; स्व-संतुलन बाइनरी सर्च ट्री की तुलना में O(log ''n'') पर आवेषण और हटा देता है। ऐसे स्थति | यदि कोई क्रमबद्ध [[गतिशील सरणी]] का उपयोग कर रहा है, तो अवयव को सम्मिलित करना और हटाना संभव है। क्रमबद्ध सरणी में अवयव का सम्मिलन और विलोपन 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 में पहला सरणी क्रमबद्ध प्रोग्राम (मर्ज क्रम में) लिखा था, जब | [[जॉन वॉन न्यूमैन]] ने 1945 में पहला सरणी क्रमबद्ध प्रोग्राम (मर्ज क्रम में) लिखा था, जब पहला संग्रहित प्रोग्राम कंप्यूटर अभी भी बनाया जा रहा था।<ref>[[Donald Knuth]], ''[[The Art of Computer Programming]]'', vol. 3. Addison-Wesley</ref> | ||
== क्रमबद्ध सरणियों के अनुप्रयोग == | == क्रमबद्ध सरणियों के अनुप्रयोग == | ||
| Line 43: | Line 43: | ||
=== प्राथमिकता निर्धारण में === | === प्राथमिकता निर्धारण में === | ||
[[ऑपरेटिंग सिस्टम|ऑपरेटिंग]] प्रणाली स्तर पर, समय में अधिक प्रक्रियाएँ लंबित होती हैं, किन्तु वे ही समय में केवल ही प्रक्रिया को संभाल सकती हैं। इसलिए, प्राथमिकताएं प्रत्येक प्रक्रिया से जुड़ी होती हैं। फिर प्रक्रिया आईडी के क्रमबद्ध सरणी का उपयोग करके प्रक्रियाओं को सर्वोच्च प्राथमिकता के अनुसार सीपीयू को भेजा जाता है। यहाँ, प्रक्रियाओं को उनकी प्राथमिकताओं के आधार पर क्रमबद्ध किया जाता है और फिर उन्हें सीपीयू आवंटित किया जाता है। उच्चतम प्राथमिकता वाली प्रक्रिया क्रमबद्ध सरणी में प्रथम स्थान लेती है। इसलिए प्राथमिकता-वार प्रणाली प्रक्रिया | [[ऑपरेटिंग सिस्टम|ऑपरेटिंग]] प्रणाली स्तर पर, समय में अधिक प्रक्रियाएँ लंबित होती हैं, किन्तु वे ही समय में केवल ही प्रक्रिया को संभाल सकती हैं। इसलिए, प्राथमिकताएं प्रत्येक प्रक्रिया से जुड़ी होती हैं। फिर प्रक्रिया आईडी के क्रमबद्ध सरणी का उपयोग करके प्रक्रियाओं को सर्वोच्च प्राथमिकता के अनुसार सीपीयू को भेजा जाता है। यहाँ, प्रक्रियाओं को उनकी प्राथमिकताओं के आधार पर क्रमबद्ध किया जाता है और फिर उन्हें सीपीयू आवंटित किया जाता है। उच्चतम प्राथमिकता वाली प्रक्रिया क्रमबद्ध सरणी में प्रथम स्थान लेती है। इसलिए प्राथमिकता-वार प्रणाली प्रक्रिया नियोजन की जाती है।<ref>{{cite book|title=ऑपरेटिंग सिस्टम की अवधारणा पीटर बी. गैल्विन द्वारा|publisher=WILEY-INDIA Pvt. limited|isbn=978-81-265-2051-0}}</ref> | ||
=== अल्पतम- कार्य-प्रथम नियोजन में === | === अल्पतम- कार्य-प्रथम नियोजन में === | ||
Revision as of 19:48, 3 March 2023
| क्रमबद्ध सरणी | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | सरणी | |||||||||||||||
| Invented | 1945 | |||||||||||||||
| Invented by | जॉन वॉन न्यूमैन | |||||||||||||||
| Time complexity in big O notation | ||||||||||||||||
| ||||||||||||||||
एक क्रमबद्ध सरणी एक सरणी डेटा संरचना है जिसमें प्रत्येक तत्व को संख्यात्मक, वर्णानुक्रमिक, या किसी अन्य क्रम में क्रमबद्ध आंकड़े है, और कंप्यूटर स्मृति में समान दूरी वाले पतों पर रखा जाता है। यह सामान्यतः कंप्यूटर विज्ञान में स्थिर और गतिशील डेटा संरचनाओं को प्रयुक्त करने के लिए उपयोग किया जाता है, जिसमें एक ही डेटा प्रकार वाले अधिक मान रखने के लिए तालिका लुकअप होते हैं। सरणी को क्रमबद्ध करना डेटा को क्रमबद्ध रूप में व्यवस्थित करने और उन्हें तेजी से पुनर्प्राप्त करने में उपयोगी होता है।
विधि
ऐसी कई जानी-मानी विधियाँ हैं जिनके द्वारा सरणी को क्रम में किया जा सकता है, जिसमें सम्मिलित हैं, किन्तुइन तक सीमित नहीं हैं: चयन प्रकार, बुलबुले की तरह, सम्मिलन क्रम, मर्ज़ क्रम, जल्दी से सुलझाएं, ढेर बनाएं और छांटें और गिनती की क्रम में इन क्रमबद्ध विधि के साथ अलग-अलग कलन विधि जुड़े हुए हैं, और इसलिए प्रत्येक विधि का उपयोग करने के अलग-अलग लाभ हैं।
अवलोकन
अनुक्रमिक रूप से संग्रहीत डेटा के लिए संदर्भ की सर्वोत्तम स्थानीयता के साथ क्रमबद्ध सरणियाँ सबसे अधिक स्थान-कुशल डेटा संरचना हैं।
एक क्रमबद्ध सरणी के अंदर अवयव को 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 |
यह भी देखें
संदर्भ
- ↑ Donald Knuth, The Art of Computer Programming, vol. 3. Addison-Wesley
- ↑ "Sorting Applications".
- ↑ ऑपरेटिंग सिस्टम की अवधारणा पीटर बी. गैल्विन द्वारा. WILEY-INDIA Pvt. limited. ISBN 978-81-265-2051-0.
