[संगीत बजाना] डौग लॉयड: चयन तरह एक है आप उम्मीद कर सकते हैं कि, एल्गोरिथ्म, तत्वों का एक सेट तरह। और एल्गोरिथ्म रिकॉल एक कदम-दर-कदम सेट है एक कार्य को पूरा करने के लिए निर्देशों का। 

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

यह इस कल्पना करने के लिए मदद मिल सकती है तो चलो इस पर एक नजर डालते हैं। तो यह है कि मैं संघर्ष, एक है अवर्गीकृत सरणी और मैं सभी यह दर्शाता है कि द्वारा यह संकेत दिया तत्वों का, लाल रंग के होते हैं वे अभी तक हल नहीं कर रहे हैं। इस पूरी है सरणी के अवर्गीकृत हिस्सा है। 

तो चलो के कदम के माध्यम से चलते हैं चयन प्रकार इस सरणी से हल करने के। तो फिर, हम लोग दोहराने रहे कोई अवर्गीकृत तत्वों रहने तक। हम के माध्यम से मिलने वाला खोज रहे हैं डेटा छोटी मूल्य खोजने के लिए, और फिर साथ कि मूल्य स्वैप अवर्गीकृत भाग के पहले तत्व। 

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

इस मामले में हो सकता है कि पाँच, तो हम एक और पांच स्वैप। हम ऐसा करते हैं, हम कर सकते हैं नेत्रहीन हम है कि वहाँ छोटी से छोटी मूल्यवान तत्व ले जाया गया सरणी के बहुत शुरुआत करने के लिए। प्रभावी ढंग से उस तत्व छँटाई। 

और इसलिए हम वास्तव में इस बात की पुष्टि कर सकते हैं और राज्य है कि एक, हल है। और इसलिए हम छाँटे गए हिस्से से संकेत मिलता हूँ हमारे सरणी की, यह नीले रंग से। 

अब हम सिर्फ फिर से इस प्रक्रिया को दोहराएँ। हम की अवर्गीकृत भाग के माध्यम से खोज सरणी छोटी तत्व खोजने के लिए। इस मामले में, यह दो है। 

हम पहले से है कि स्वैप अवर्गीकृत भाग के तत्व। इस मामले में दो को भी होना होता है अवर्गीकृत भाग के पहले तत्व। तो हम खुद के साथ दो स्वैप, जो वास्तव में सिर्फ दो पत्ते यह है, और यह हल है जहां। पर सतत, हम के माध्यम से खोज छोटी तत्व खोजने के लिए। यह तीन है। हम पहले से यह स्वैप पांच है जो तत्व। और अब तीन हल है। 

हम फिर से खोज के माध्यम से, और हम छोटी तत्व चार है लगता है। हम के पहले तत्व के साथ यह स्वैप अवर्गीकृत हिस्सा है, और अब चार हल है। 

हम पाँच लगता है कि छोटी तत्व। हम पहले से यह स्वैप अवर्गीकृत भाग के तत्व। और अब पांच हल है। 

और फिर अंत में, हमारे अवर्गीकृत हिस्सा होते हैं सिर्फ एक ही तत्व की, इसलिए हम के माध्यम से खोज और हम छह है कि लगता है छोटी से छोटी है, और वास्तव में, केवल तत्व। और फिर हम इसे हल किया है कि राज्य कर सकते हैं। और अब हम हमारे सरणी बंद कर दिया है पूरी तरह से unsorted जा रहा से लाल रंग में पूरी तरह से हल करने के लिए नीले रंग में, चयन तरह इस्तेमाल करते हैं। 

तो सबसे बुरी स्थिति यहां क्या हो रहा है? खैर निरपेक्ष बुरी में मामला है, हम पर देखने के लिए है सरणी के तत्वों के सभी छोटी से छोटी अवर्गीकृत तत्व मिल जाए, और हम दोहराने के लिए है इस प्रक्रिया n बार। सरणी के प्रत्येक तत्व के लिए एक बार हम केवल क्योंकि, इस एल्गोरिथ्म में, समय पर तरह एक तत्व। 

सबसे अच्छी स्थिति क्या है? वैसे यह सही है, बिल्कुल वैसा ही है? हम वास्तव में अभी भी माध्यम से कदम है सरणी के हर एक तत्व क्रम में, यह है कि इस बात की पुष्टि करने के लिए वास्तव में, छोटी तत्व। 

तो सबसे ज्यादा मामले क्रम में, हम एक प्रक्रिया n बार दोहराने के लिए है, n तत्वों से प्रत्येक के लिए एक बार। और सबसे अच्छी स्थिति में, हम भी ऐसा ही करने के लिए है। 

तो वापस करने के लिए सोच हमारे कम्प्यूटेशनल जटिलता उपकरण बॉक्स, क्या आपको लगता है कि सबसे खराब है चयन प्रकार के लिए मामला क्रम? क्या आपको लगता है कि सबसे अच्छा है चयन प्रकार के लिए मामला क्रम? 

N चुकता की आप बड़ी हे लगता था, और बिग ओमेगा n चुकता? तुम सही होगा। उन लोगों के हैं, वास्तव में, सबसे खराब स्थिति और सबसे अच्छा मामले रन चयन प्रकार के लिए समय है,। 

मैं डौग लॉयड हूँ। इस CS50 है।