आंशिक सॉर्टिंग एल्गोरिदम

Question

कहें कि मेरे पास 50 मिलियन विशेषताएं हैं, प्रत्येक सुविधा डिस्क से आती है।

मेरे कार्यक्रम की भिक्षा पर, मैं प्रत्येक सुविधा को संभालता हूं और कुछ स्थितियों के आधार पर, मैं कुछ में कुछ संशोधन लागू करता हूं।

मेरे कार्यक्रम में यह बिंदु, मैं डिस्क से एक सुविधा पढ़ रहा हूं, इसे संसाधित कर रहा हूं, और इसे वापस लिख रहा हूं, क्योंकि मेरे पास एक ही समय में सभी 50 मिलियन विशेषताओं को खोलने के लिए पर्याप्त RAM नहीं है।

अब कहें कि मैं इन 50 मिलियन विशेषताओं को सॉर्ट करना चाहता हूं, क्या ऐसा करने के लिए कोई इष्टतम एल्गोरिदम है क्योंकि मैं एक ही समय में सभी को लोड नहीं कर सकता?

आंशिक सॉर्टिंग एल्गोरिदम या ऐसा कुछ पसंद है?

Answer 1

सामान्यतः, एल्गोरिदम की श्रेणी जिसे आप ढूंढ रहे हैं उसे external sorting कहा जाता है। शायद इस तरह के सॉर्टिंग एल्गोरिदम का सबसे व्यापक उदाहरण Merge sort कहा जाता है।

इस एल्गोरिदम (बाहरी संस्करण) का विचार यह है कि आप डेटा को उन टुकड़ों में विभाजित करते हैं जिन्हें आप स्मृति में क्रमबद्ध कर सकते हैं (100 हजार कहें) और प्रत्येक ब्लॉक को स्वतंत्र रूप से क्रमबद्ध करें (Quick sort जैसे कुछ मानक एल्गोरिदम का उपयोग करके) । फिर आप ब्लॉक लेते हैं और उन्हें मर्ज करते हैं (इसलिए आप दो 100k ब्लॉक को एक 200k ब्लॉक में विलय करते हैं) जो दोनों ब्लॉक से तत्वों को बफर में पढ़कर किया जा सकता है (क्योंकि ब्लॉक पहले ही सॉर्ट किए गए हैं)। अंत में, आप दो ब्लॉक को एक ब्लॉक में विलय करते हैं जिसमें सभी तत्व सही क्रम में होंगे।

Answer 2

आप यूनिक्स पर कर रहे हैं, sort का उपयोग करें;)

यह बेवकूफ लग सकता है, लेकिन आदेश-पंक्ति उपकरण इस मामले को संभालने के लिए प्रोग्राम किया गया है और आप इसे रिप्रोग्राम की ज़रूरत नहीं होगी।