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

2
00:00:03,360 --> 00:00:04,522

3
00:00:04,522 --> 00:00:06,730
डौग लॉयड: ठीक है, तो
बुलबुला तरह एक एल्गोरिथ्म है

4
00:00:06,730 --> 00:00:08,730
आप तत्वों का एक सेट से सुलझाने के लिए उपयोग कर सकते हैं।

5
00:00:08,730 --> 00:00:10,850
चलो यह कैसे काम करता है पर एक नज़र रखना।

6
00:00:10,850 --> 00:00:13,240
>> तो मूल विचार के पीछे
बुलबुला तरह यह है।

7
00:00:13,240 --> 00:00:17,340
हम आम तौर पर उच्च स्थानांतरित करना चाहते हैं
आम तौर पर सही करने के लिए मूल्यवान तत्व,

8
00:00:17,340 --> 00:00:20,340
और आम तौर पर मूल्यवान तत्व कम
बाईं ओर है, हम उम्मीद करेंगे।

9
00:00:20,340 --> 00:00:23,256
हम कम चीजों में रहना चाहता हूँ
शुरुआत है, और उच्च बातें

10
00:00:23,256 --> 00:00:24,970
अंत में किया जाना है।

11
00:00:24,970 --> 00:00:26,130
>> हम इसे कैसे करते हैं?

12
00:00:26,130 --> 00:00:28,040
खैर स्यूडोकोड कोड में,
हम चलो, कह सकते हैं

13
00:00:28,040 --> 00:00:30,320
एक गैर शून्य मान के लिए एक स्वैप काउंटर निर्धारित किया है।

14
00:00:30,320 --> 00:00:32,570
हम एक दूसरे में है कि ऐसा क्यों हम देखेंगे।

15
00:00:32,570 --> 00:00:36,090
और फिर हम निम्नलिखित दोहराने
स्वैप काउंटर 0 है जब तक प्रक्रिया,

16
00:00:36,090 --> 00:00:39,910
या हम सब में कोई स्वैप जब तक।

17
00:00:39,910 --> 00:00:43,170
>> करने के लिए स्वैप काउंटर रीसेट
0 यह पहले से ही शून्य नहीं है।

18
00:00:43,170 --> 00:00:46,420
तब से हर देखो
तत्वों के आसन्न जोड़ी।

19
00:00:46,420 --> 00:00:49,550
उन दो तत्व हैं, तो
नहीं, क्रम में उन्हें स्वैप,

20
00:00:49,550 --> 00:00:51,620
और स्वैप मुकाबला करने के लिए 1 जोड़ें।

21
00:00:51,620 --> 00:00:53,870
आप के बारे में सोच रहे हैं
यह आप यह कल्पना से पहले,

22
00:00:53,870 --> 00:00:57,471
यह कम कदम होगा कि नोटिस
बाईं ओर मूल्यवान तत्व

23
00:00:57,471 --> 00:01:00,720
और अधिक है, सही करने के लिए तत्वों मूल्यवान
प्रभावी ढंग से हम क्या करना चाहते हैं कर रही है,

24
00:01:00,720 --> 00:01:03,940
जो उन समूहों के लिए कदम है
कि रास्ते में तत्वों की।

25
00:01:03,940 --> 00:01:07,035
चलो कैसे यह कल्पना करते हैं
हमारे सरणी का उपयोग कर लग सकता है

26
00:01:07,035 --> 00:01:10,504
हम परीक्षण करने के लिए इस्तेमाल किया है कि
इन एल्गोरिदम बाहर।

27
00:01:10,504 --> 00:01:13,420
हम यहाँ फिर से एक अवर्गीकृत सरणी है
तत्वों के सभी ने संकेत दिया

28
00:01:13,420 --> 00:01:14,840
लाल रंग में किया जा रहा है।

29
00:01:14,840 --> 00:01:17,970
और मुझे लगता है मेरे स्वैप काउंटर सेट
एक अशून्य मूल्य के लिए।

30
00:01:17,970 --> 00:01:20,610
मैं मनमाने ढंग से चुना
नकारात्मक 1-- यह 0 नहीं है।

31
00:01:20,610 --> 00:01:23,840
हम इस प्रक्रिया को दोहराना चाहते हैं
स्वैप काउंटर तक 0 है।

32
00:01:23,840 --> 00:01:26,540
मैं मेरे स्वैप सेट यही कारण है
कुछ गैर-शून्य मान के लिए काउंटर,

33
00:01:26,540 --> 00:01:29,400
अन्यथा क्योंकि
स्वैप काउंटर 0 होगा।

34
00:01:29,400 --> 00:01:31,610
हम भी शुरू नहीं होगा
एल्गोरिथ्म की प्रक्रिया।

35
00:01:31,610 --> 00:01:33,610
तो फिर, कदम are--
स्वैप काउंटर रीसेट

36
00:01:33,610 --> 00:01:37,900
0 करने के लिए, तो हर आसन्न को देखो
जोड़ी है, और वे आदेश से बाहर कर रहे हैं,

37
00:01:37,900 --> 00:01:40,514
उन्हें स्वैप, और 1 जोड़ने
स्वैप मुकाबला करने के लिए।

38
00:01:40,514 --> 00:01:41,680
तो चलो इस प्रक्रिया को शुरू करते हैं।

39
00:01:41,680 --> 00:01:44,430
इसलिए हम ऐसा पहली बात है
हम 0 करने के लिए स्वैप काउंटर सेट

40
00:01:44,430 --> 00:01:46,660
और फिर हम तलाश शुरू
प्रत्येक आसन्न जोड़ी पर।

41
00:01:46,660 --> 00:01:49,140
>> इसलिए हम पहले 5 और 2 को देख शुरू।

42
00:01:49,140 --> 00:01:52,410
हम वे से बाहर हैं कि वहाँ
आदेश और इसलिए हम उन्हें स्वैप।

43
00:01:52,410 --> 00:01:53,830
और हम स्वैप मुकाबला करने के लिए 1 जोड़ें।

44
00:01:53,830 --> 00:01:57,860
तो अब हमारे स्वैप काउंटर 1 है,
और 2 और 5 के लिए बंद कर दिया गया है।

45
00:01:57,860 --> 00:01:59,370
अब हम फिर से इस प्रक्रिया को दोहराने।

46
00:01:59,370 --> 00:02:03,540
>> हम अगले आसन्न जोड़ी को देखो,
5 और वे भी आदेश से बाहर रहे हैं 1--,

47
00:02:03,540 --> 00:02:06,960
इसलिए हम उन्हें स्वैप और जोड़ने
स्वैप मुकाबला करने के लिए 1।

48
00:02:06,960 --> 00:02:08,900
तो फिर हम 5 और 3 पर दिखेगा।

49
00:02:08,900 --> 00:02:13,830
वे क्रम से बाहर हैं, इसलिए हम स्वैप
उन्हें और हम स्वैप मुकाबला करने के लिए 1 जोड़ें।

50
00:02:13,830 --> 00:02:15,550
तो फिर हम 5 और 6 को देखो।

51
00:02:15,550 --> 00:02:18,630
वे क्रम में कर रहे हैं, इसलिए हम वास्तव में नहीं है
कुछ भी इस समय स्वैप करने की जरूरत है।

52
00:02:18,630 --> 00:02:20,250
तो फिर हम 6 और 4 को देखो।

53
00:02:20,250 --> 00:02:24,920
वे आदेश से बाहर भी कर रहे हैं, तो हम स्वैप
उन्हें और हम स्वैप मुकाबला करने के लिए 1 जोड़ें।

54
00:02:24,920 --> 00:02:26,230
>> अब क्या हुआ है नोटिस।

55
00:02:26,230 --> 00:02:29,514
हम अंत करने के लिए 6 से सभी तरह से चला गया है।

56
00:02:29,514 --> 00:02:32,180
चयन प्रकार में तो, तुम हो, तो
कि वीडियो देखा, क्या हमने किया था

57
00:02:32,180 --> 00:02:35,290
हम आगे बढ़ समाप्त हो गया
इमारत में सबसे छोटी तत्वों

58
00:02:35,290 --> 00:02:39,640
अनिवार्य रूप से सॉर्ट सरणी
सबसे बड़ा करने के लिए, सबसे छोटी सही करने के लिए छोड़ दिया है।

59
00:02:39,640 --> 00:02:43,200
बुलबुला तरह के मामले में, हम कर रहे हैं
इस विशेष एल्गोरिथ्म के बाद,

60
00:02:43,200 --> 00:02:46,720
हम वास्तव में निर्माण करने जा रहे हैं
सही से हल सरणी

61
00:02:46,720 --> 00:02:49,100
छोटी करने के लिए, सबसे बड़ा छोड़ दिया करने के लिए।

62
00:02:49,100 --> 00:02:53,840
हम प्रभावी रूप से 6, bubbled है
सबसे बड़ा मान, समाप्त करने के लिए सभी तरह।

63
00:02:53,840 --> 00:02:56,165
>> और इसलिए हम अब घोषणा कर सकते हैं
कि हल है कि,

64
00:02:56,165 --> 00:02:59,130
और भविष्य में iterations--
सरणी के माध्यम से जा रहा again--

65
00:02:59,130 --> 00:03:01,280
हम अब और 6 पर विचार करने की जरूरत नहीं है।

66
00:03:01,280 --> 00:03:03,850
हम केवल विचार करना होगा
अवर्गीकृत तत्वों

67
00:03:03,850 --> 00:03:06,299
जब हम आसन्न जोड़े को देख रहे हैं।

68
00:03:06,299 --> 00:03:08,340
इसलिए हम एक समाप्त कर दिया है
बुलबुला प्रकार के माध्यम से गुजरती हैं।

69
00:03:08,340 --> 00:03:11,941
तो अब हम सवाल करने के लिए वापस जाना है,
स्वैप काउंटर 0 है जब तक दोहराएँ।

70
00:03:11,941 --> 00:03:13,690
खैर स्वैप काउंटर
4 है, इसलिए हम जा रहे हैं

71
00:03:13,690 --> 00:03:15,410
फिर इस प्रक्रिया को दोहरा रखने के लिए।

72
00:03:15,410 --> 00:03:19,180
>> हम स्वैप काउंटर रीसेट करने के लिए जा रहे हैं
0 करने के लिए, और प्रत्येक आसन्न जोड़ी को देखो।

73
00:03:19,180 --> 00:03:21,890
तो हम वे कर रहे हैं 1-- 2 के साथ शुरू और
आदेश से बाहर है, इसलिए हम उन्हें स्वैप

74
00:03:21,890 --> 00:03:23,620
और हम स्वैप मुकाबला करने के लिए 1 जोड़ें।

75
00:03:23,620 --> 00:03:25,490
2 और 3, वे क्रम में कर रहे हैं।

76
00:03:25,490 --> 00:03:27,060
हम कुछ भी करने की जरूरत नहीं।

77
00:03:27,060 --> 00:03:28,420
3 और 5 के क्रम में हैं।

78
00:03:28,420 --> 00:03:30,150
हम वहाँ कुछ करने की ज़रूरत नहीं है।

79
00:03:30,150 --> 00:03:32,515
>> 5 और 4, वे बाहर हैं
आदेश के, और इसलिए हम

80
00:03:32,515 --> 00:03:35,130
उन्हें स्वैप और जोड़ने की जरूरत
स्वैप मुकाबला करने के लिए 1।

81
00:03:35,130 --> 00:03:38,880
और अब हम, 5 स्थानांतरित किया है
अगले सबसे बड़ा तत्व है,

82
00:03:38,880 --> 00:03:40,920
अवर्गीकृत भाग के अंत करने के लिए।

83
00:03:40,920 --> 00:03:44,360
तो क्या अब हम कह सकते हैं कि
छाँटे गए हिस्से का हिस्सा है।

84
00:03:44,360 --> 00:03:47,180
>> अब आप देख रहे हैं
स्क्रीन और शायद बता सकते हैं,

85
00:03:47,180 --> 00:03:50,130
मैं कर सकता हूँ सरणी कि के रूप में
अब सही हल है।

86
00:03:50,130 --> 00:03:51,820
लेकिन हम अभी तक यह साबित नहीं कर सकते हैं।

87
00:03:51,820 --> 00:03:54,359
हम एक गारंटी नहीं है
कि यह हल है।

88
00:03:54,359 --> 00:03:56,900
लेकिन इस जहां स्वैप है
काउंटर खेल में आने के लिए जा रहा है।

89
00:03:56,900 --> 00:03:59,060
>> इसलिए हम एक पास पूरा कर दिया है।

90
00:03:59,060 --> 00:04:00,357
स्वैप काउंटर 2 है।

91
00:04:00,357 --> 00:04:02,190
इसलिए हम दोहराने के लिए जा रहे हैं
इस प्रक्रिया को फिर,

92
00:04:02,190 --> 00:04:04,290
स्वैप काउंटर 0 है जब तक दोहराएँ।

93
00:04:04,290 --> 00:04:05,550
0 करने के लिए स्वैप काउंटर रीसेट।

94
00:04:05,550 --> 00:04:06,820
तो हम इसे फिर से कायम करेंगे।

95
00:04:06,820 --> 00:04:09,810
>> अब प्रत्येक आसन्न जोड़ी को देखो।

96
00:04:09,810 --> 00:04:11,880
यही कारण है कि आदेश में 1 और 2 है।

97
00:04:11,880 --> 00:04:13,590
2 और 3 के क्रम में हैं।

98
00:04:13,590 --> 00:04:15,010
3 और 4 के क्रम में हैं।

99
00:04:15,010 --> 00:04:19,250
तो इस बिंदु पर, हम पूरा कर दिया नोटिस
हर आसन्न जोड़ी को देख,

100
00:04:19,250 --> 00:04:22,530
लेकिन स्वैप काउंटर अभी भी शून्य है।

101
00:04:22,530 --> 00:04:25,520
>> हम स्विच करने के लिए नहीं है, तो
किसी भी तत्व हैं, वे तो

102
00:04:25,520 --> 00:04:28,340
द्वारा, क्रम में होना चाहिए
इस प्रक्रिया के आधार पर।

103
00:04:28,340 --> 00:04:32,000
और इसलिए एक तरह की एक दक्षता,
कि हम कंप्यूटर वैज्ञानिकों से प्यार है,

104
00:04:32,000 --> 00:04:35,560
हम अब घोषणा कर सकते है
पूरे सरणी चाहिए

105
00:04:35,560 --> 00:04:38,160
हम नहीं किया, क्योंकि हल किया जा
किसी भी तत्व को स्वैप करने के लिए है।

106
00:04:38,160 --> 00:04:40,380
यह बहुत अच्छा है।

107
00:04:40,380 --> 00:04:43,260
>> तो क्या सबसे खराब मामला है
बुलबुला तरह से परिदृश्य?

108
00:04:43,260 --> 00:04:46,240
सबसे खराब स्थिति में सरणी है
पूरी तरह से रिवर्स क्रम में,

109
00:04:46,240 --> 00:04:49,870
और इसलिए हम प्रत्येक बुलबुला करना है
बड़े तत्वों के सभी

110
00:04:49,870 --> 00:04:51,780
सरणी पार तरीका है।

111
00:04:51,780 --> 00:04:55,350
और हम प्रभावी रूप से भी करने की जरूरत
बुलबुला छोटे तत्वों के सभी वापस

112
00:04:55,350 --> 00:04:57,050
बहुत सरणी भर में सभी तरह।

113
00:04:57,050 --> 00:05:01,950
इसलिए n तत्वों में से प्रत्येक कदम है
अन्य n तत्वों के सभी भर में।

114
00:05:01,950 --> 00:05:04,102
तो यह है कि सबसे बुरी स्थिति है।

115
00:05:04,102 --> 00:05:05,810
बेहतर स्थिति में
परिदृश्य हालांकि, यह है

116
00:05:05,810 --> 00:05:07,880
चयन प्रकार से थोड़ा अलग है।

117
00:05:07,880 --> 00:05:10,040
सरणी पहले से ही है
हम में जाने के लिए जब सुलझा लिया।

118
00:05:10,040 --> 00:05:12,550
हम किसी भी बनाने की जरूरत नहीं है
पहले पारित पर स्वैप।

119
00:05:12,550 --> 00:05:14,940
इसलिए हम देखने के लिए हो सकता है
कम तत्वों पर, है ना?

120
00:05:14,940 --> 00:05:18,580
हम यह दोहराने की जरूरत नहीं है
से अधिक समय की एक नंबर की प्रक्रिया।

121
00:05:18,580 --> 00:05:19,540
>> तो उसका क्या मतलब हुआ?

122
00:05:19,540 --> 00:05:22,390
तो क्या हुआ अगर सबसे खराब स्थिति है
बुलबुला तरह के लिए, और क्या है

123
00:05:22,390 --> 00:05:25,330
बुलबुला तरह के लिए सबसे अच्छी स्थिति?

124
00:05:25,330 --> 00:05:27,770
आप इस अनुमान था?

125
00:05:27,770 --> 00:05:32,420
सबसे खराब स्थिति में आप पुनरावृति करने के लिए है
सभी n तत्वों n बार के पार।

126
00:05:32,420 --> 00:05:34,220
तो सबसे ज्यादा मामले n चुकता है।

127
00:05:34,220 --> 00:05:36,550
>> सरणी पूरी तरह से है
सॉर्ट हालांकि, आप केवल

128
00:05:36,550 --> 00:05:38,580
प्रत्येक को देखने के लिए
एक बार तत्वों की।

129
00:05:38,580 --> 00:05:42,670
और स्वैप काउंटर अभी भी शून्य है,
आप इस सरणी हल है कह सकते हैं।

130
00:05:42,670 --> 00:05:45,780
और इसलिए सबसे अच्छा मामले में, यह है
चयन से वास्तव में बेहतर

131
00:05:45,780 --> 00:05:49,230
sort-- यह n के ओमेगा है।

132
00:05:49,230 --> 00:05:50,270
>> मैं डौग लॉयड हूँ।

133
00:05:50,270 --> 00:05:52,140
इस CS50 है।

134
00:05:52,140 --> 00:05:54,382