[Powered by Google Translate] टॉमी: चलो चयन छंटाई, एक एल्गोरिथ्म पर एक नज़र रखना
संख्याओं की एक सूची ले रही है और उन्हें छँटाई के लिए.
एक एल्गोरिथ्म, याद है, बस एक कदम दर कदम है
एक कार्य को पूरा करने के लिए प्रक्रिया.
चयन छंटाई के पीछे मूल विचार को विभाजित करने के लिए है
दो भागों में हमारी सूची -
एक क्रमबद्ध भाग और एक unsorted भाग.
एल्गोरिथ्म के हर कदम पर, एक नंबर से ले जाया जाता है
अंततः जब तक क्रमबद्ध भाग unsorted भाग
पूरी सूची हल है.
तो यहाँ छह नंबर की एक सूची है -
23, 42, 4, 16, 8, और 15.
अभी पूरी सूची unsorted माना जाता है.
हालांकि 16 की तरह एक नंबर पहले से ही इसकी सही में हो सकता है
स्थान, हमारे एल्गोरिथ्म है कि जब तक जानने का कोई तरीका नहीं है
पूरी सूची हल है.
इसलिए हम हर संख्या पर विचार करने के लिए unsorted जा सकता है जब तक हम सुलझा लेंगे
यह खुद.
हम जानते हैं कि हम सूची आरोही क्रम में होना चाहते हैं.
तो हम हमारी सूची के हल हिस्से का निर्माण करने के लिए चाहता हूँ
बाएँ से दाएँ, सबसे बड़ा करने के लिए छोटी है.
ऐसा करने के लिए, हम करने के लिए कम से कम unsorted तत्व खोजने की आवश्यकता होगी
और यह क्रमबद्ध भाग के अंत में डाल.
इस सूची के बाद से हल नहीं है, एक ही तरीका है कि
unsorted भाग में प्रत्येक तत्व में देखो, याद
जो तत्व निम्नतम और तुलना
कि प्रत्येक तत्व.
तो हम 1 से 23 में देख लेंगे.
यह पहला तत्व है कि हमने देखा है, तो हम याद करेंगे
यह कम से कम के रूप में.
हम अगले 42 में देख लेंगे.
42 23 की तुलना में बड़ा है, इसलिए 23 अभी भी न्यूनतम है.
अगले 4 है जो कम से कम 23 है, तो हम 4 याद करेंगे
नए न्यूनतम के रूप में.
अगला 16 है जो 4 से भी बड़ा है, इतना 4
अभी भी कम से कम है.
8 4 की तुलना में बड़ा है, और 15 4 की तुलना में बड़ा है तो 4 होना चाहिए
छोटी unsorted तत्व.
तो भले ही मनुष्य के रूप में हम तुरंत देखते हैं कि 4 है
न्यूनतम तत्व, हमारे एल्गोरिथ्म को देखने की जरूरत है
हर unsorted तत्व, के बाद भी हम 4 पाया है -
न्यूनतम तत्व.
तो अब है कि हम कम से कम तत्व, 4 पाया है, हम चाहते हैं
यह सूची के अनुसार क्रमबद्ध भाग में स्थानांतरित.
के बाद से यह पहला कदम है, इस का मतलब है कि हम 4 डाल करना चाहते हैं
सूची की शुरुआत.
23 अभी सूची की शुरुआत में ऐसा है,
चलो 4 और 23 स्वैप.
तो अब हमारी सूची इस तरह लग रहा है.
हम जानते हैं कि 4 अपने अंतिम स्थान में होना चाहिए, क्योंकि यह है
दोनों छोटी और शुरुआत में तत्व तत्व
सूची के.
तो इसका मतलब है कि हम कभी इसे फिर से बढ़ने की जरूरत नहीं है.
तो चलो करने के लिए एक और तत्व जोड़ने के लिए इस प्रक्रिया को दोहराने
सूची के अनुसार क्रमबद्ध भाग.
हम जानते हैं कि हम 4 में देखने की जरूरत नहीं है, क्योंकि यह है
पहले से ही हल.
इसलिए हम 42 में शुरू कर सकते हैं, जो हम के रूप में याद करेंगे
न्यूनतम तत्व.
हम तो अगली हम 23 है जो 42 से भी कम समय है पर देखने हूँ, तो
याद है 23 नए न्यूनतम है.
हम अगले 16 है, जो कम से कम 23 है तो देखते हैं,
16 नए न्यूनतम है.
अब हम 8 है जो कम से कम 16 है तो देखो,
8 नए न्यूनतम है.
और अंत में 8 कम से कम 15 है, इसलिए हम जानते हैं कि कि 8 एक न्यूनतम है
unsorted तत्व.
तो इसका मतलब है कि हम 8 हल के लिए संलग्न करना चाहिए
सूची के भाग.
अभी 4 ही क्रमबद्ध तत्व है, तो हम जगह करना चाहते हैं
8 4 के बगल में.
42 के बाद से की unsorted भाग में पहला तत्व है
सूची, हम 42 और 8 स्वैप करने के लिए चाहता हूँ.
तो अब हमारी सूची इस तरह लग रहा है.
4 और 8 सूची के अनुसार क्रमबद्ध हिस्से का प्रतिनिधित्व करते हैं, और
शेष संख्या unsorted का प्रतिनिधित्व करते हैं
सूची के भाग.
तो चलो एक और यात्रा के साथ जारी है.
हम 23 के साथ इस समय के लिए शुरू के बाद से हम को देखने की जरूरत नहीं है
4 और 8 क्योंकि अब वे है
पहले से ही हल किया गया.
16 कम से कम 23 है, तो हम याद करेंगे
16 नए न्यूनतम के रूप में.
16 कम से कम 42 है, लेकिन कम से कम 15 16 है, तो 15 होना चाहिए
न्यूनतम unsorted तत्व.
तो अब हम 15 और 23 स्वैप करना चाहते हैं
हमें इस सूची दे.
सूची के अनुसार क्रमबद्ध भाग 8 4 और 15 के होते हैं, और
इन तत्वों unsorted अभी भी कर रहे हैं.
लेकिन यह सिर्फ इतना होता है कि अगले unsorted तत्व, 16,
पहले से ही हल.
हालांकि, हमारे एल्गोरिथ्म के लिए कोई रास्ता नहीं पता चला है कि 16
उसके सही स्थान में पहले से ही है, इसलिए हम अभी भी जरूरत है
ठीक उसी प्रक्रिया को दोहराएँ.
तो हम देखते हैं कि 16 कम से कम 42 है, और 16 कम से कम 23 है,
16 न्यूनतम तत्व होना चाहिए.
यह असंभव है करने के लिए खुद के साथ इस तत्व स्वैप तो, हम कर सकते हैं
बस इसे इस स्थान में छोड़ दें.
तो हम हमारे एल्गोरिथ्म के एक और पास की जरूरत है.
42 23 से अधिक है, तो 23 होना चाहिए
न्यूनतम unsorted तत्व.
एक बार जब हम 23 और 42 स्वैप, हम अपने अंतिम साथ खत्म
क्रमबद्ध सूची -
4, 8, 15, 16, 23, 42.
हम जानते हैं कि 42 सही जगह में हो सकता है क्योंकि यह
केवल तत्व छोड़ दिया है, और है कि चयन की तरह है.
चलो अब कुछ के साथ हमारे एल्गोरिथ्म शकल
pseudocode.
एक लाइन में, हम देख सकते हैं कि हम पर एकीकृत करने की आवश्यकता है
सूची के प्रत्येक तत्व.
के बाद से अंतिम तत्व को छोड़कर, 1 तत्व
सूची पहले से ही हल है.
लाइन दो पर, हम unsorted के पहले तत्व पर विचार
सूची के भाग को न्यूनतम करने के लिए, के रूप में हम हमारे साथ किया था
उदाहरण के लिए, तो हम करने के लिए की तुलना करने के लिए कुछ है.
तीन लाइन 2 पाश में जो हम पर पुनरावृति करने के लिए शुरू होता है
प्रत्येक unsorted तत्व.
हम जानते हैं कि मैं पुनरूक्तियाँ के बाद, हल भाग
हमारी सूची के प्रत्येक चरण के बाद से मैं इसे में तत्वों का होना चाहिए
एक तत्व प्रकार.
तो 1 unsorted तत्व मैं प्लस 1 स्थिति में होना चाहिए.
चार लाइन पर हम कम से कम करने के लिए वर्तमान तत्व की तुलना
तत्व है कि हम अब तक देखा है.
यदि वर्तमान तत्व न्यूनतम से छोटी है
तत्व है, तो हम नए रूप में वर्तमान तत्व याद
लाइन पर कम से कम पाँच.
अंत में, छह और सात लाइनों पर, हम कम से कम स्वैप
1 unsorted तत्व के साथ इस तरह तत्व,
यह सूची के अनुसार क्रमबद्ध भाग को जोड़ने.
एक बार जब हम एक एल्गोरिथ्म है, एक महत्वपूर्ण सवाल पूछने के लिए
खुद प्रोग्रामर के रूप में लंबे समय है कि कैसे ले गए थे?
हम पहला सवाल पूछता हूँ कि कितनी देर तक यह इस बात के लिए ले करता है
सबसे खराब स्थिति में चलाने के लिए एल्गोरिथ्म?
याद है हम यह चल रहा है का प्रतिनिधित्व करते हैं
बड़ी हे संकेतन के साथ समय.
आदेश में न्यूनतम unsorted तत्व निर्धारित करने के लिए, हम
अनिवार्य रूप से करने के लिए सूची में प्रत्येक तत्व की तुलना करने के लिए किया था
सूची में हर दूसरे तत्व.
Intuitively, इस n चुकता आपरेशन के एक हे की तरह लगता है.
हमारे pseudocode को देखते हुए, हम भी एक अंदर नेस्टेड पाश है
एक और एक हे जैसे पाश है जो वास्तव में लगता है
n चुकता आपरेशन के.
लेकिन याद रखें कि हम पर देखने की जरूरत नहीं था
पूरी सूची जब न्यूनतम unsorted तत्व का निर्धारण?
एक बार हम जानते थे कि 4 क्रमबद्ध किया गया था, उदाहरण के लिए किया था, हम नहीं
इसे फिर से देखने की जरूरत है.
तो इस समय चल रहा करता है कम?
6 लंबाई की हमारी सूची के लिए, हम पाँच बनाने की जरूरत
पहले तत्व के लिए तुलना, के लिए चार तुलना
दूसरा तत्व है, और इतने पर.
इसका मतलब है कि कदम की कुल संख्या का योग है
1 से 1 शून्य सूची की लंबाई integers.
हम एक संकलन के साथ इस का प्रतिनिधित्व कर सकते हैं.
हम summations में यहाँ नहीं जाना होगा.
लेकिन यह पता चला है कि इस समेशन n बार के बराबर है
n ऋण 1 2 से अधिक.
या equivalently, n पर 2 शून्य से 2 से अधिक n चुकता.
जब asymptotic क्रम के बारे में बात कर रही है, इस n चुकता अवधि
इस n शब्द पर हावी हो रहा है.
तो चयन छंटाई n चुकता हे है.
याद है कि हमारे उदाहरण में, चयन छंटाई अभी भी करने की जरूरत है
अगर जांच एक संख्या है कि पहले से ही हल किया गया था
करने के लिए ले जाया जा जरूरत है.
तो इसका मतलब है कि अगर हम पहले से ही एक से अधिक चयन छंटाई भागा
सूची हल, यह यह कदम के रूप में एक ही नंबर की आवश्यकता होगी
होगा जब एक पूरी तरह से unsorted सूची पर चल रहा है.
तो चयन छंटाई चुकता n के मामले का प्रदर्शन किया है,
जो हम साथ ओमेगा n चुकता प्रतिनिधित्व.
और कहा कि यह चयन छंटाई के लिए है.
बस कई एल्गोरिदम हम कर सकते हैं
एक सूची तरह का उपयोग करें.
मेरा नाम टॉमी है, और इस CS50 है.