1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] टॉमी: चलो चयन छंटाई, एक एल्गोरिथ्म पर एक नज़र रखना

2
00:00:09,980 --> 00:00:12,800
संख्याओं की एक सूची ले रही है और उन्हें छँटाई के लिए.

3
00:00:12,800 --> 00:00:15,750
एक एल्गोरिथ्म, याद है, बस एक कदम दर कदम है

4
00:00:15,750 --> 00:00:18,370
एक कार्य को पूरा करने के लिए प्रक्रिया.

5
00:00:18,370 --> 00:00:21,470
चयन छंटाई के पीछे मूल विचार को विभाजित करने के लिए है

6
00:00:21,470 --> 00:00:23,390
दो भागों में हमारी सूची -

7
00:00:23,390 --> 00:00:26,810
एक क्रमबद्ध भाग और एक unsorted भाग.

8
00:00:26,810 --> 00:00:30,200
एल्गोरिथ्म के हर कदम पर, एक नंबर से ले जाया जाता है

9
00:00:30,200 --> 00:00:33,800
अंततः जब तक क्रमबद्ध भाग unsorted भाग

10
00:00:33,800 --> 00:00:35,880
पूरी सूची हल है.

11
00:00:35,880 --> 00:00:38,510
तो यहाँ छह नंबर की एक सूची है -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, और 15.

13
00:00:44,010 --> 00:00:47,680
अभी पूरी सूची unsorted माना जाता है.

14
00:00:47,680 --> 00:00:51,770
हालांकि 16 की तरह एक नंबर पहले से ही इसकी सही में हो सकता है

15
00:00:51,770 --> 00:00:56,040
स्थान, हमारे एल्गोरिथ्म है कि जब तक जानने का कोई तरीका नहीं है

16
00:00:56,040 --> 00:00:57,980
पूरी सूची हल है.

17
00:00:57,980 --> 00:01:01,355
इसलिए हम हर संख्या पर विचार करने के लिए unsorted जा सकता है जब तक हम सुलझा लेंगे

18
00:01:01,355 --> 00:01:03,800
यह खुद.

19
00:01:03,800 --> 00:01:06,890
हम जानते हैं कि हम सूची आरोही क्रम में होना चाहते हैं.

20
00:01:06,890 --> 00:01:10,200
तो हम हमारी सूची के हल हिस्से का निर्माण करने के लिए चाहता हूँ

21
00:01:10,200 --> 00:01:13,280
बाएँ से दाएँ, सबसे बड़ा करने के लिए छोटी है.

22
00:01:13,280 --> 00:01:17,970
ऐसा करने के लिए, हम करने के लिए कम से कम unsorted तत्व खोजने की आवश्यकता होगी

23
00:01:17,970 --> 00:01:21,350
और यह क्रमबद्ध भाग के अंत में डाल.

24
00:01:21,350 --> 00:01:25,370
इस सूची के बाद से हल नहीं है, एक ही तरीका है कि

25
00:01:25,370 --> 00:01:29,330
unsorted भाग में प्रत्येक तत्व में देखो, याद

26
00:01:29,330 --> 00:01:32,010
जो तत्व निम्नतम और तुलना

27
00:01:32,010 --> 00:01:33,770
कि प्रत्येक तत्व.

28
00:01:33,770 --> 00:01:36,150
तो हम 1 से 23 में देख लेंगे.

29
00:01:36,150 --> 00:01:38,650
यह पहला तत्व है कि हमने देखा है, तो हम याद करेंगे

30
00:01:38,650 --> 00:01:40,050
यह कम से कम के रूप में.

31
00:01:40,050 --> 00:01:42,320
हम अगले 42 में देख लेंगे.

32
00:01:42,320 --> 00:01:46,720
42 23 की तुलना में बड़ा है, इसलिए 23 अभी भी न्यूनतम है.

33
00:01:46,720 --> 00:01:51,210
अगले 4 है जो कम से कम 23 है, तो हम 4 याद करेंगे

34
00:01:51,210 --> 00:01:52,880
नए न्यूनतम के रूप में.

35
00:01:52,880 --> 00:01:56,380
अगला 16 है जो 4 से भी बड़ा है, इतना 4

36
00:01:56,380 --> 00:01:57,980
अभी भी कम से कम है.

37
00:01:57,980 --> 00:02:03,670
8 4 की तुलना में बड़ा है, और 15 4 की तुलना में बड़ा है तो 4 होना चाहिए

38
00:02:03,670 --> 00:02:05,980
छोटी unsorted तत्व.

39
00:02:05,980 --> 00:02:09,350
तो भले ही मनुष्य के रूप में हम तुरंत देखते हैं कि 4 है

40
00:02:09,350 --> 00:02:12,300
न्यूनतम तत्व, हमारे एल्गोरिथ्म को देखने की जरूरत है

41
00:02:12,300 --> 00:02:15,710
हर unsorted तत्व, के बाद भी हम 4 पाया है -

42
00:02:15,710 --> 00:02:16,860
न्यूनतम तत्व.

43
00:02:16,860 --> 00:02:19,900
तो अब है कि हम कम से कम तत्व, 4 पाया है, हम चाहते हैं

44
00:02:19,900 --> 00:02:23,410
यह सूची के अनुसार क्रमबद्ध भाग में स्थानांतरित.

45
00:02:23,410 --> 00:02:27,320
के बाद से यह पहला कदम है, इस का मतलब है कि हम 4 डाल करना चाहते हैं

46
00:02:27,320 --> 00:02:29,680
सूची की शुरुआत.

47
00:02:29,680 --> 00:02:33,040
23 अभी सूची की शुरुआत में ऐसा है,

48
00:02:33,040 --> 00:02:36,080
चलो 4 और 23 स्वैप.

49
00:02:36,080 --> 00:02:38,870
तो अब हमारी सूची इस तरह लग रहा है.

50
00:02:38,870 --> 00:02:42,710
हम जानते हैं कि 4 अपने अंतिम स्थान में होना चाहिए, क्योंकि यह है

51
00:02:42,710 --> 00:02:45,890
दोनों छोटी और शुरुआत में तत्व तत्व

52
00:02:45,890 --> 00:02:46,960
सूची के.

53
00:02:46,960 --> 00:02:50,650
तो इसका मतलब है कि हम कभी इसे फिर से बढ़ने की जरूरत नहीं है.

54
00:02:50,650 --> 00:02:53,910
तो चलो करने के लिए एक और तत्व जोड़ने के लिए इस प्रक्रिया को दोहराने

55
00:02:53,910 --> 00:02:55,910
सूची के अनुसार क्रमबद्ध भाग.

56
00:02:55,910 --> 00:02:58,950
हम जानते हैं कि हम 4 में देखने की जरूरत नहीं है, क्योंकि यह है

57
00:02:58,950 --> 00:03:00,000
पहले से ही हल.

58
00:03:00,000 --> 00:03:03,540
इसलिए हम 42 में शुरू कर सकते हैं, जो हम के रूप में याद करेंगे

59
00:03:03,540 --> 00:03:05,290
न्यूनतम तत्व.

60
00:03:05,290 --> 00:03:08,700
हम तो अगली हम 23 है जो 42 से भी कम समय है पर देखने हूँ, तो

61
00:03:08,700 --> 00:03:11,620
याद है 23 नए न्यूनतम है.

62
00:03:11,620 --> 00:03:14,870
हम अगले 16 है, जो कम से कम 23 है तो देखते हैं,

63
00:03:14,870 --> 00:03:16,800
16 नए न्यूनतम है.

64
00:03:16,800 --> 00:03:19,720
अब हम 8 है जो कम से कम 16 है तो देखो,

65
00:03:19,720 --> 00:03:21,130
8 नए न्यूनतम है.

66
00:03:21,130 --> 00:03:25,900
और अंत में 8 कम से कम 15 है, इसलिए हम जानते हैं कि कि 8 एक न्यूनतम है

67
00:03:25,900 --> 00:03:27,780
unsorted तत्व.

68
00:03:27,780 --> 00:03:30,660
तो इसका मतलब है कि हम 8 हल के लिए संलग्न करना चाहिए

69
00:03:30,660 --> 00:03:32,450
सूची के भाग.

70
00:03:32,450 --> 00:03:35,990
अभी 4 ही क्रमबद्ध तत्व है, तो हम जगह करना चाहते हैं

71
00:03:35,990 --> 00:03:38,410
8 4 के बगल में.

72
00:03:38,410 --> 00:03:41,920
42 के बाद से की unsorted भाग में पहला तत्व है

73
00:03:41,920 --> 00:03:47,260
सूची, हम 42 और 8 स्वैप करने के लिए चाहता हूँ.

74
00:03:47,260 --> 00:03:49,680
तो अब हमारी सूची इस तरह लग रहा है.

75
00:03:49,680 --> 00:03:53,830
4 और 8 सूची के अनुसार क्रमबद्ध हिस्से का प्रतिनिधित्व करते हैं, और

76
00:03:53,830 --> 00:03:56,440
शेष संख्या unsorted का प्रतिनिधित्व करते हैं

77
00:03:56,440 --> 00:03:58,260
सूची के भाग.

78
00:03:58,260 --> 00:04:00,630
तो चलो एक और यात्रा के साथ जारी है.

79
00:04:00,630 --> 00:04:03,850
हम 23 के साथ इस समय के लिए शुरू के बाद से हम को देखने की जरूरत नहीं है

80
00:04:03,850 --> 00:04:05,770
4 और 8 क्योंकि अब वे है

81
00:04:05,770 --> 00:04:07,660
पहले से ही हल किया गया.

82
00:04:07,660 --> 00:04:10,270
16 कम से कम 23 है, तो हम याद करेंगे

83
00:04:10,270 --> 00:04:12,070
16 नए न्यूनतम के रूप में.

84
00:04:12,070 --> 00:04:18,149
16 कम से कम 42 है, लेकिन कम से कम 15 16 है, तो 15 होना चाहिए

85
00:04:18,149 --> 00:04:20,480
न्यूनतम unsorted तत्व.

86
00:04:20,480 --> 00:04:24,580
तो अब हम 15 और 23 स्वैप करना चाहते हैं

87
00:04:24,580 --> 00:04:26,310
हमें इस सूची दे.

88
00:04:26,310 --> 00:04:30,500
सूची के अनुसार क्रमबद्ध भाग 8 4 और 15 के होते हैं, और

89
00:04:30,500 --> 00:04:33,210
इन तत्वों unsorted अभी भी कर रहे हैं.

90
00:04:33,210 --> 00:04:36,900
लेकिन यह सिर्फ इतना होता है कि अगले unsorted तत्व, 16,

91
00:04:36,900 --> 00:04:38,480
पहले से ही हल.

92
00:04:38,480 --> 00:04:42,060
हालांकि, हमारे एल्गोरिथ्म के लिए कोई रास्ता नहीं पता चला है कि 16

93
00:04:42,060 --> 00:04:45,230
उसके सही स्थान में पहले से ही है, इसलिए हम अभी भी जरूरत है

94
00:04:45,230 --> 00:04:47,870
ठीक उसी प्रक्रिया को दोहराएँ.

95
00:04:47,870 --> 00:04:53,750
तो हम देखते हैं कि 16 कम से कम 42 है, और 16 कम से कम 23 है,

96
00:04:53,750 --> 00:04:56,230
16 न्यूनतम तत्व होना चाहिए.

97
00:04:56,230 --> 00:04:59,010
यह असंभव है करने के लिए खुद के साथ इस तत्व स्वैप तो, हम कर सकते हैं

98
00:04:59,010 --> 00:05:01,780
बस इसे इस स्थान में छोड़ दें.

99
00:05:01,780 --> 00:05:04,660
तो हम हमारे एल्गोरिथ्म के एक और पास की जरूरत है.

100
00:05:04,660 --> 00:05:09,370
42 23 से अधिक है, तो 23 होना चाहिए

101
00:05:09,370 --> 00:05:10,970
न्यूनतम unsorted तत्व.

102
00:05:10,970 --> 00:05:17,410
एक बार जब हम 23 और 42 स्वैप, हम अपने अंतिम साथ खत्म

103
00:05:17,410 --> 00:05:18,530
क्रमबद्ध सूची -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
हम जानते हैं कि 42 सही जगह में हो सकता है क्योंकि यह

106
00:05:26,830 --> 00:05:30,210
केवल तत्व छोड़ दिया है, और है कि चयन की तरह है.

107
00:05:30,210 --> 00:05:32,100
चलो अब कुछ के साथ हमारे एल्गोरिथ्म शकल

108
00:05:32,100 --> 00:05:34,540
pseudocode.

109
00:05:34,540 --> 00:05:37,760
एक लाइन में, हम देख सकते हैं कि हम पर एकीकृत करने की आवश्यकता है

110
00:05:37,760 --> 00:05:39,530
सूची के प्रत्येक तत्व.

111
00:05:39,530 --> 00:05:42,150
के बाद से अंतिम तत्व को छोड़कर, 1 तत्व

112
00:05:42,150 --> 00:05:44,230
सूची पहले से ही हल है.

113
00:05:44,230 --> 00:05:48,100
लाइन दो पर, हम unsorted के पहले तत्व पर विचार

114
00:05:48,100 --> 00:05:51,080
सूची के भाग को न्यूनतम करने के लिए, के रूप में हम हमारे साथ किया था

115
00:05:51,080 --> 00:05:53,750
उदाहरण के लिए, तो हम करने के लिए की तुलना करने के लिए कुछ है.

116
00:05:53,750 --> 00:05:57,260
तीन लाइन 2 पाश में जो हम पर पुनरावृति करने के लिए शुरू होता है

117
00:05:57,260 --> 00:05:59,170
प्रत्येक unsorted तत्व.

118
00:05:59,170 --> 00:06:02,150
हम जानते हैं कि मैं पुनरूक्तियाँ के बाद, हल भाग

119
00:06:02,150 --> 00:06:05,330
हमारी सूची के प्रत्येक चरण के बाद से मैं इसे में तत्वों का होना चाहिए

120
00:06:05,330 --> 00:06:06,890
एक तत्व प्रकार.

121
00:06:06,890 --> 00:06:11,770
तो 1 unsorted तत्व मैं प्लस 1 स्थिति में होना चाहिए.

122
00:06:11,770 --> 00:06:15,440
चार लाइन पर हम कम से कम करने के लिए वर्तमान तत्व की तुलना

123
00:06:15,440 --> 00:06:17,750
तत्व है कि हम अब तक देखा है.

124
00:06:17,750 --> 00:06:20,560
यदि वर्तमान तत्व न्यूनतम से छोटी है

125
00:06:20,560 --> 00:06:23,870
तत्व है, तो हम नए रूप में वर्तमान तत्व याद

126
00:06:23,870 --> 00:06:26,250
लाइन पर कम से कम पाँच.

127
00:06:26,250 --> 00:06:29,900
अंत में, छह और सात लाइनों पर, हम कम से कम स्वैप

128
00:06:29,900 --> 00:06:33,080
1 unsorted तत्व के साथ इस तरह तत्व,

129
00:06:33,080 --> 00:06:36,990
यह सूची के अनुसार क्रमबद्ध भाग को जोड़ने.

130
00:06:36,990 --> 00:06:40,030
एक बार जब हम एक एल्गोरिथ्म है, एक महत्वपूर्ण सवाल पूछने के लिए

131
00:06:40,030 --> 00:06:43,370
खुद प्रोग्रामर के रूप में लंबे समय है कि कैसे ले गए थे?

132
00:06:43,370 --> 00:06:46,970
हम पहला सवाल पूछता हूँ कि कितनी देर तक यह इस बात के लिए ले करता है

133
00:06:46,970 --> 00:06:50,070
सबसे खराब स्थिति में चलाने के लिए एल्गोरिथ्म?

134
00:06:50,070 --> 00:06:51,640
याद है हम यह चल रहा है का प्रतिनिधित्व करते हैं

135
00:06:51,640 --> 00:06:55,060
बड़ी हे संकेतन के साथ समय.

136
00:06:55,060 --> 00:06:58,650
आदेश में न्यूनतम unsorted तत्व निर्धारित करने के लिए, हम

137
00:06:58,650 --> 00:07:01,880
अनिवार्य रूप से करने के लिए सूची में प्रत्येक तत्व की तुलना करने के लिए किया था

138
00:07:01,880 --> 00:07:04,040
सूची में हर दूसरे तत्व.

139
00:07:04,040 --> 00:07:08,430
Intuitively, इस n चुकता आपरेशन के एक हे की तरह लगता है.

140
00:07:08,430 --> 00:07:12,050
हमारे pseudocode को देखते हुए, हम भी एक अंदर नेस्टेड पाश है

141
00:07:12,050 --> 00:07:14,420
एक और एक हे जैसे पाश है जो वास्तव में लगता है

142
00:07:14,420 --> 00:07:16,480
n चुकता आपरेशन के.

143
00:07:16,480 --> 00:07:19,250
लेकिन याद रखें कि हम पर देखने की जरूरत नहीं था

144
00:07:19,250 --> 00:07:23,460
पूरी सूची जब न्यूनतम unsorted तत्व का निर्धारण?

145
00:07:23,460 --> 00:07:26,600
एक बार हम जानते थे कि 4 क्रमबद्ध किया गया था, उदाहरण के लिए किया था, हम नहीं

146
00:07:26,600 --> 00:07:28,170
इसे फिर से देखने की जरूरत है.

147
00:07:28,170 --> 00:07:31,020
तो इस समय चल रहा करता है कम?

148
00:07:31,020 --> 00:07:34,510
6 लंबाई की हमारी सूची के लिए, हम पाँच बनाने की जरूरत

149
00:07:34,510 --> 00:07:37,990
पहले तत्व के लिए तुलना, के लिए चार तुलना

150
00:07:37,990 --> 00:07:40,750
दूसरा तत्व है, और इतने पर.

151
00:07:40,750 --> 00:07:44,690
इसका मतलब है कि कदम की कुल संख्या का योग है

152
00:07:44,690 --> 00:07:49,160
1 से 1 शून्य सूची की लंबाई integers.

153
00:07:49,160 --> 00:07:51,005
हम एक संकलन के साथ इस का प्रतिनिधित्व कर सकते हैं.

154
00:07:57,980 --> 00:07:59,910
हम summations में यहाँ नहीं जाना होगा.

155
00:07:59,910 --> 00:08:04,900
लेकिन यह पता चला है कि इस समेशन n बार के बराबर है

156
00:08:04,900 --> 00:08:07,540
n ऋण 1 2 से अधिक.

157
00:08:07,540 --> 00:08:14,220
या equivalently, n पर 2 शून्य से 2 से अधिक n चुकता.

158
00:08:14,220 --> 00:08:18,860
जब asymptotic क्रम के बारे में बात कर रही है, इस n चुकता अवधि

159
00:08:18,860 --> 00:08:22,070
इस n शब्द पर हावी हो रहा है.

160
00:08:22,070 --> 00:08:27,850
तो चयन छंटाई n चुकता हे है.

161
00:08:27,850 --> 00:08:31,460
याद है कि हमारे उदाहरण में, चयन छंटाई अभी भी करने की जरूरत है

162
00:08:31,460 --> 00:08:33,850
अगर जांच एक संख्या है कि पहले से ही हल किया गया था

163
00:08:33,850 --> 00:08:35,450
करने के लिए ले जाया जा जरूरत है.

164
00:08:35,450 --> 00:08:38,929
तो इसका मतलब है कि अगर हम पहले से ही एक से अधिक चयन छंटाई भागा

165
00:08:38,929 --> 00:08:43,070
सूची हल, यह यह कदम के रूप में एक ही नंबर की आवश्यकता होगी

166
00:08:43,070 --> 00:08:46,340
होगा जब एक पूरी तरह से unsorted सूची पर चल रहा है.

167
00:08:46,340 --> 00:08:51,470
तो चयन छंटाई चुकता n के मामले का प्रदर्शन किया है,

168
00:08:51,470 --> 00:08:56,820
जो हम साथ ओमेगा n चुकता प्रतिनिधित्व.

169
00:08:56,820 --> 00:08:58,600
और कहा कि यह चयन छंटाई के लिए है.

170
00:08:58,600 --> 00:09:00,630
बस कई एल्गोरिदम हम कर सकते हैं

171
00:09:00,630 --> 00:09:02,390
एक सूची तरह का उपयोग करें.

172
00:09:02,390 --> 00:09:05,910
मेरा नाम टॉमी है, और इस CS50 है.