1
00:00:00,000 --> 00:00:05,726
>> [संगीत बजाना]

2
00:00:05,726 --> 00:00:08,600
डौग लॉयड: चयन तरह एक है
आप उम्मीद कर सकते हैं कि, एल्गोरिथ्म,

3
00:00:08,600 --> 00:00:10,470
तत्वों का एक सेट तरह।

4
00:00:10,470 --> 00:00:12,470
और एल्गोरिथ्म रिकॉल
एक कदम-दर-कदम सेट है

5
00:00:12,470 --> 00:00:15,260
एक कार्य को पूरा करने के लिए निर्देशों का।

6
00:00:15,260 --> 00:00:17,580
>> चयन में क्रमबद्ध
मूल विचार यह है

7
00:00:17,580 --> 00:00:22,080
छोटी से छोटी अवर्गीकृत तत्व खोजने के लिए और
क्रमबद्ध सूची के अंत में जोड़ें।

8
00:00:22,080 --> 00:00:26,970
प्रभावी ढंग से इस क्या करता है, का निर्माण होता है
एक क्रमबद्ध सूची, एक समय में एक तत्व।

9
00:00:26,970 --> 00:00:29,800
स्यूडोकोड करने के लिए यह तोड़कर नीचे
हम इस एल्गोरिथ्म राज्य सकता है

10
00:00:29,800 --> 00:00:34,490
इस प्रकार है, जब तक यह दोहराना
कोई अवर्गीकृत तत्व रहते हैं।

11
00:00:34,490 --> 00:00:38,660
अवर्गीकृत के माध्यम से खोज
डेटा छोटी मूल्य खोजने के लिए,

12
00:00:38,660 --> 00:00:44,130
उसके बाद से सबसे छोटा मान स्वैप
अवर्गीकृत भाग के पहले तत्व।

13
00:00:44,130 --> 00:00:47,130
>> यह इस कल्पना करने के लिए मदद मिल सकती है
तो चलो इस पर एक नजर डालते हैं।

14
00:00:47,130 --> 00:00:49,710
तो यह है कि मैं संघर्ष, एक है
अवर्गीकृत सरणी और मैं

15
00:00:49,710 --> 00:00:53,040
सभी यह दर्शाता है कि द्वारा यह संकेत दिया
तत्वों का, लाल रंग के होते हैं

16
00:00:53,040 --> 00:00:54,420
वे अभी तक हल नहीं कर रहे हैं।

17
00:00:54,420 --> 00:00:57,670
इस पूरी है
सरणी के अवर्गीकृत हिस्सा है।

18
00:00:57,670 --> 00:01:02,020
>> तो चलो के कदम के माध्यम से चलते हैं
चयन प्रकार इस सरणी से हल करने के।

19
00:01:02,020 --> 00:01:05,296
तो फिर, हम लोग दोहराने रहे
कोई अवर्गीकृत तत्वों रहने तक।

20
00:01:05,296 --> 00:01:07,920
हम के माध्यम से मिलने वाला खोज रहे हैं
डेटा छोटी मूल्य खोजने के लिए,

21
00:01:07,920 --> 00:01:11,990
और फिर साथ कि मूल्य स्वैप
अवर्गीकृत भाग के पहले तत्व।

22
00:01:11,990 --> 00:01:14,380
>> अभी, फिर पूरे
सरणी अवर्गीकृत हिस्सा है।

23
00:01:14,380 --> 00:01:16,534
लाल तत्वों के सभी अवर्गीकृत हैं।

24
00:01:16,534 --> 00:01:18,700
इसलिए हम के माध्यम से खोज और
हम छोटी मूल्य लगता है।

25
00:01:18,700 --> 00:01:20,533
हम शुरुआत में शुरू
हम अंत में जाना

26
00:01:20,533 --> 00:01:23,630
हम छोटी मूल्य, एक है लगता है।

27
00:01:23,630 --> 00:01:24,860
तो यह है कि एक हिस्सा है।

28
00:01:24,860 --> 00:01:29,440
और फिर भाग दो, के साथ कि मूल्य स्वैप
अवर्गीकृत भाग के पहले तत्व,

29
00:01:29,440 --> 00:01:31,340
या पहले लाल तत्व।

30
00:01:31,340 --> 00:01:34,980
>> इस मामले में हो सकता है कि
पाँच, तो हम एक और पांच स्वैप।

31
00:01:34,980 --> 00:01:37,320
हम ऐसा करते हैं, हम कर सकते हैं
नेत्रहीन हम है कि वहाँ

32
00:01:37,320 --> 00:01:41,260
छोटी से छोटी मूल्यवान तत्व ले जाया गया
सरणी के बहुत शुरुआत करने के लिए।

33
00:01:41,260 --> 00:01:43,920
प्रभावी ढंग से उस तत्व छँटाई।

34
00:01:43,920 --> 00:01:47,520
>> और इसलिए हम वास्तव में इस बात की पुष्टि कर सकते हैं
और राज्य है कि एक, हल है।

35
00:01:47,520 --> 00:01:52,080
और इसलिए हम छाँटे गए हिस्से से संकेत मिलता हूँ
हमारे सरणी की, यह नीले रंग से।

36
00:01:52,080 --> 00:01:53,860
>> अब हम सिर्फ फिर से इस प्रक्रिया को दोहराएँ।

37
00:01:53,860 --> 00:01:57,430
हम की अवर्गीकृत भाग के माध्यम से खोज
सरणी छोटी तत्व खोजने के लिए।

38
00:01:57,430 --> 00:01:59,000
इस मामले में, यह दो है।

39
00:01:59,000 --> 00:02:02,100
>> हम पहले से है कि स्वैप
अवर्गीकृत भाग के तत्व।

40
00:02:02,100 --> 00:02:05,540
इस मामले में दो को भी होना होता है
अवर्गीकृत भाग के पहले तत्व।

41
00:02:05,540 --> 00:02:08,650
तो हम खुद के साथ दो स्वैप,
जो वास्तव में सिर्फ दो पत्ते

42
00:02:08,650 --> 00:02:11,257
यह है, और यह हल है जहां।

43
00:02:11,257 --> 00:02:13,840
पर सतत, हम के माध्यम से खोज
छोटी तत्व खोजने के लिए।

44
00:02:13,840 --> 00:02:15,030
यह तीन है।

45
00:02:15,030 --> 00:02:17,650
हम पहले से यह स्वैप
पांच है जो तत्व।

46
00:02:17,650 --> 00:02:19,450
और अब तीन हल है।

47
00:02:19,450 --> 00:02:22,440
>> हम फिर से खोज के माध्यम से, और हम
छोटी तत्व चार है लगता है।

48
00:02:22,440 --> 00:02:28,070
हम के पहले तत्व के साथ यह स्वैप
अवर्गीकृत हिस्सा है, और अब चार हल है।

49
00:02:28,070 --> 00:02:29,910
>> हम पाँच लगता है कि
छोटी तत्व।

50
00:02:29,910 --> 00:02:32,900
हम पहले से यह स्वैप
अवर्गीकृत भाग के तत्व।

51
00:02:32,900 --> 00:02:34,740
और अब पांच हल है।

52
00:02:34,740 --> 00:02:36,660
>> और फिर अंत में, हमारे
अवर्गीकृत हिस्सा होते हैं

53
00:02:36,660 --> 00:02:38,576
सिर्फ एक ही तत्व की,
इसलिए हम के माध्यम से खोज

54
00:02:38,576 --> 00:02:41,740
और हम छह है कि लगता है
छोटी से छोटी है, और वास्तव में, केवल तत्व।

55
00:02:41,740 --> 00:02:44,906
और फिर हम इसे हल किया है कि राज्य कर सकते हैं।

56
00:02:44,906 --> 00:02:47,530
और अब हम हमारे सरणी बंद कर दिया है
पूरी तरह से unsorted जा रहा से

57
00:02:47,530 --> 00:02:52,660
लाल रंग में पूरी तरह से हल करने के लिए
नीले रंग में, चयन तरह इस्तेमाल करते हैं।

58
00:02:52,660 --> 00:02:54,920
>> तो सबसे बुरी स्थिति यहां क्या हो रहा है?

59
00:02:54,920 --> 00:02:57,830
खैर निरपेक्ष बुरी में
मामला है, हम पर देखने के लिए है

60
00:02:57,830 --> 00:03:02,170
सरणी के तत्वों के सभी
छोटी से छोटी अवर्गीकृत तत्व मिल जाए,

61
00:03:02,170 --> 00:03:04,750
और हम दोहराने के लिए है
इस प्रक्रिया n बार।

62
00:03:04,750 --> 00:03:09,090
सरणी के प्रत्येक तत्व के लिए एक बार
हम केवल क्योंकि, इस एल्गोरिथ्म में,

63
00:03:09,090 --> 00:03:12,180
समय पर तरह एक तत्व।

64
00:03:12,180 --> 00:03:13,595
>> सबसे अच्छी स्थिति क्या है?

65
00:03:13,595 --> 00:03:15,040
वैसे यह सही है, बिल्कुल वैसा ही है?

66
00:03:15,040 --> 00:03:18,440
हम वास्तव में अभी भी माध्यम से कदम है
सरणी के हर एक तत्व

67
00:03:18,440 --> 00:03:22,040
क्रम में, यह है कि इस बात की पुष्टि करने के लिए
वास्तव में, छोटी तत्व।

68
00:03:22,040 --> 00:03:26,760
>> तो सबसे ज्यादा मामले क्रम में, हम
एक प्रक्रिया n बार दोहराने के लिए है,

69
00:03:26,760 --> 00:03:28,960
n तत्वों से प्रत्येक के लिए एक बार।

70
00:03:28,960 --> 00:03:31,940
और सबसे अच्छी स्थिति में,
हम भी ऐसा ही करने के लिए है।

71
00:03:31,940 --> 00:03:35,340
>> तो वापस करने के लिए सोच हमारे
कम्प्यूटेशनल जटिलता उपकरण बॉक्स,

72
00:03:35,340 --> 00:03:39,250
क्या आपको लगता है कि सबसे खराब है
चयन प्रकार के लिए मामला क्रम?

73
00:03:39,250 --> 00:03:41,840
क्या आपको लगता है कि सबसे अच्छा है
चयन प्रकार के लिए मामला क्रम?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> N चुकता की आप बड़ी हे लगता था,
और बिग ओमेगा n चुकता?

76
00:03:49,325 --> 00:03:49,950
तुम सही होगा।

77
00:03:49,950 --> 00:03:52,490
उन लोगों के हैं, वास्तव में,
सबसे खराब स्थिति और सबसे अच्छा मामले रन

78
00:03:52,490 --> 00:03:55,100
चयन प्रकार के लिए समय है,।

79
00:03:55,100 --> 00:03:56,260
>> मैं डौग लॉयड हूँ।

80
00:03:56,260 --> 00:03:58,600
इस CS50 है।

81
00:03:58,600 --> 00:04:00,279