1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [बुलबुला तरह]

2
00:00:02,840 --> 00:00:04,560
[जैक्सन STEINKAMP हार्वर्ड विश्वविद्यालय]

3
00:00:04,560 --> 00:00:07,500
[इस CS50 है. CS50TV]

4
00:00:08,000 --> 00:00:11,730
बुलबुला तरह एक छँटाई एल्गोरिथ्म का एक उदाहरण है -

5
00:00:11,730 --> 00:00:14,460
कि है, तत्वों का एक सेट में छंटनी करने के लिए एक प्रक्रिया

6
00:00:14,460 --> 00:00:15,840
आरोही या अवरोही क्रम.

7
00:00:15,840 --> 00:00:18,710
उदाहरण के लिए, यदि आप एक सरणी तरह चाहता था संख्या से मिलकर

8
00:00:18,710 --> 00:00:23,060
[3, 5, 2, 9], बुलबुला तरह के एक सही कार्यान्वयन लौटेंगे

9
00:00:23,060 --> 00:00:26,260
क्रमबद्ध [2, 3, 5, 9] सरणी आरोही क्रम में.

10
00:00:26,260 --> 00:00:28,850
अब, मैं pseudocode में व्याख्या कैसे एल्गोरिथ्म काम करता जा रहा हूँ.

11
00:00:28,850 --> 00:00:34,000
>> चलो कहते हैं कि हम 5 पूर्णांकों की एक सूची छँटाई कर रहे हैं - 3, 2, 9, 6, और 5.

12
00:00:34,000 --> 00:00:37,650
एल्गोरिथ्म पहले दो तत्वों, 3 और 2 पर देख द्वारा शुरू होता है,

13
00:00:37,650 --> 00:00:40,850
और जाँच अगर वे एक दूसरे के सापेक्ष आदेश से बाहर रहे हैं.

14
00:00:40,850 --> 00:00:43,150
वे हैं - तीन दो से अधिक है.

15
00:00:43,150 --> 00:00:45,190
आरोही क्रम में हो सकता है, वे अन्य तरह के आसपास होना चाहिए.

16
00:00:45,190 --> 00:00:46,610
इसलिए, हम उन्हें स्वैप.

17
00:00:46,610 --> 00:00:49,760
[2, 3, 9, 6, 5]: अब सूची इस तरह लग रहा है.

18
00:00:49,760 --> 00:00:52,450
>> अगला, हम दूसरे और तीसरे तत्वों, 3 और 9 पर दिखेगा.

19
00:00:52,450 --> 00:00:55,770
वे सही क्रम में एक दूसरे के रिश्तेदार हैं.

20
00:00:55,770 --> 00:00:58,800
यही कारण है, 3 9 से कम इतना एल्गोरिथ्म उन्हें स्वैप नहीं करता है.

21
00:00:58,800 --> 00:01:01,900
अगला, हम 9 और 6 में देखो. वे आदेश से बाहर रहे हैं.

22
00:01:01,900 --> 00:01:04,260
>> तो, हम उन्हें स्वैप है क्योंकि 9 6 से अधिक है की जरूरत है.

23
00:01:04,260 --> 00:01:08,840
अन्त में, हम पिछले दो integers, 9 और 5 को देखो.

24
00:01:08,840 --> 00:01:10,850
वे आदेश के बाहर हैं, तो वे बदली किया जाना चाहिए.

25
00:01:10,850 --> 00:01:13,360
सूची के माध्यम से पहले पूरा पास के बाद,

26
00:01:13,360 --> 00:01:17,140
[2, 3, 6, 5, 9]: यह इस तरह दिखता है.

27
00:01:17,140 --> 00:01:19,690
बुरा नहीं है. यह लगभग हल है.

28
00:01:19,690 --> 00:01:22,450
लेकिन हम सूची के माध्यम से फिर से चलाने के लिए यह पूरी तरह से क्रमबद्ध करने की जरूरत है.

29
00:01:22,450 --> 00:01:29,250
दो 3 की तुलना में कम है, तो हम उन्हें स्वैप नहीं.

30
00:01:29,250 --> 00:01:31,700
>> तीन 6 की तुलना में कम है, तो हम उन्हें स्वैप नहीं.

31
00:01:31,700 --> 00:01:35,500
छह 5 से अधिक है. हम बदली.

32
00:01:35,500 --> 00:01:38,460
9 से छह कम है. हम स्वैप नहीं.

33
00:01:38,460 --> 00:01:42,170
2 के माध्यम से पारित करने के बाद, यह इस तरह दिखता है: [2, 3, 5, 6, 9]. बिल्कुल सही.

34
00:01:42,170 --> 00:01:44,680
अब, चलो यह pseudocode में लिखने के.

35
00:01:44,680 --> 00:01:48,450
असल में, सूची में प्रत्येक तत्व के लिए, हम इसे देखने की जरूरत है

36
00:01:48,450 --> 00:01:50,060
और सीधे इसकी सही तत्व.

37
00:01:50,060 --> 00:01:53,420
यदि वे आदेश के बाहर एक दूसरे के रिश्तेदार हैं - जो है, अगर बाईं तरफ तत्व

38
00:01:53,420 --> 00:01:56,810
सही पर एक से अधिक है - हम दो तत्वों स्वैप चाहिए.

39
00:01:56,810 --> 00:02:01,270
>> हम सूची के प्रत्येक तत्व के लिए ऐसा करते हैं, और हम के माध्यम से एक पास कर दिया है.

40
00:02:01,270 --> 00:02:05,160
अब हम सिर्फ पास के माध्यम से पर्याप्त समय सूची में करने के लिए सुनिश्चित करने के लिए है

41
00:02:05,160 --> 00:02:06,480
पूरी तरह से ठीक से हल.

42
00:02:06,480 --> 00:02:08,889
लेकिन कितनी बार हम सूची के माध्यम से पारित है

43
00:02:08,889 --> 00:02:10,400
गारंटी है कि हम कर रहे हैं?

44
00:02:10,400 --> 00:02:14,730
खैर, सबसे खराब स्थिति यह है कि अगर हम एक पूरी तरह से पीछे की ओर सूची.

45
00:02:14,730 --> 00:02:17,840
तो यह पारित throughs की संख्या के बराबर संख्या लेता है

46
00:02:17,840 --> 00:02:19,730
n-1 तत्वों की.

47
00:02:19,730 --> 00:02:24,720
यदि यह भावना intuitively नहीं पड़ता है, एक साधारण मामला है के बारे में सोच - सूची [2, 1].

48
00:02:24,720 --> 00:02:28,430
>> यह एक पास के माध्यम से लेने के लिए सही ढंग से सॉर्ट जा रहा है.

49
00:02:28,430 --> 00:02:33,060
[3, 2, 1] - सबसे खराब मामला है कि 3 तत्वों के साथ पीछे की ओर क्रमबद्ध

50
00:02:33,060 --> 00:02:34,830
यह तरह 2 पुनरावृत्तियों ले जा रहा है.

51
00:02:34,830 --> 00:02:37,980
एक चलना के बाद, यह [2, 1, 3] है.

52
00:02:37,980 --> 00:02:39,550
2 पैदावार क्रमबद्ध सरणी [1, 2, 3].

53
00:02:39,550 --> 00:02:43,350
तो आप जानते हैं कि आप सामान्य रूप में कभी नहीं किया है, सरणी के माध्यम से जाना है,

54
00:02:43,350 --> 00:02:46,790
n-1 बार, जहाँ n सरणी में तत्वों की संख्या की तुलना में अधिक है.

55
00:02:47,090 --> 00:02:50,470
यह बुलबुला तरह कहा जाता है, क्योंकि सबसे बड़ा तत्वों 'बुलबुला' के लिए करते हैं

56
00:02:50,470 --> 00:02:51,950
सही करने के लिए बहुत जल्दी.

57
00:02:51,950 --> 00:02:53,980
वास्तव में, इस एल्गोरिथ्म व्यवहार बहुत ही रोचक है.

58
00:02:53,980 --> 00:02:57,410
>> पूरे सरणी के माध्यम से मीटर iterations के बाद,

59
00:02:57,410 --> 00:02:59,000
rightmost मीटर तत्वों की गारंटी हैं

60
00:02:59,000 --> 00:03:01,000
उनके सही जगह में हल किया जा.

61
00:03:01,000 --> 00:03:02,280
अगर आप खुद के लिए यह देखना चाहते हैं,

62
00:03:02,280 --> 00:03:05,500
हम इसे पूरी तरह से पीछे की ओर [9, 6, 5, 3, 2] सूची पर कोशिश कर सकते हैं.

63
00:03:05,500 --> 00:03:08,220
पूरी सूची के माध्यम से एक पास के बाद,

64
00:03:08,220 --> 00:03:09,220
लेखन की ध्वनि []

65
00:03:09,220 --> 00:03:18,790
[6, 9, 5, 2, 3], [6, 5, 9, 3 2,], [6, 5, 3, 9 2,], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
rightmost 9 तत्व अपनी सही जगह में है.

67
00:03:21,250 --> 00:03:24,760
पास के माध्यम से 2 के बाद 6 'bubbled अप' होगा

68
00:03:24,760 --> 00:03:26,220
2 rightmost जगह.

69
00:03:26,220 --> 00:03:28,840
6 और 9 - सही पर दो तत्वों को उनके सही स्थानों में होगा

70
00:03:28,840 --> 00:03:30,580
पहले दो पास - थ्रू के बाद.

71
00:03:30,580 --> 00:03:32,590
>> तो, हम कैसे इस का उपयोग एल्गोरिथ्म अनुकूलन कर सकते हैं?

72
00:03:32,590 --> 00:03:34,850
खैर, सरणी के माध्यम से एक चलना के बाद

73
00:03:34,850 --> 00:03:37,690
हम वास्तव rightmost तत्व की जांच की जरूरत नहीं है

74
00:03:37,690 --> 00:03:39,200
क्योंकि हम जानते हैं कि यह हल है.

75
00:03:39,200 --> 00:03:43,050
दो iterations के बाद, हम सुनिश्चित करें कि rightmost दो तत्वों जगह में हैं के लिए जानते हैं.

76
00:03:43,050 --> 00:03:48,260
तो, सामान्य रूप में, पूर्ण सरणी के माध्यम से कश्मीर पुनरावृत्तियों के बाद,

77
00:03:48,260 --> 00:03:51,550
पिछले कश्मीर तत्वों की जाँच निरर्थक है क्योंकि हम जानते हैं

78
00:03:51,550 --> 00:03:52,360
वे सही स्थान में पहले से ही कर रहे हैं.

79
00:03:52,360 --> 00:03:54,870
>> तो अगर आप n तत्वों की एक सरणी छँटाई कर रहे हैं,

80
00:03:54,870 --> 00:03:57,870
पहली यात्रा पर you'll तत्वों के सभी प्रकार है - 1 n-0.

81
00:03:57,870 --> 00:04:04,170
दूसरी यात्रा पर, आप तत्वों के सभी लेकिन पिछले पर देखना होगा -

82
00:04:04,170 --> 00:04:07,090
n-1 1.

83
00:04:07,090 --> 00:04:10,520
एक अन्य अनुकूलन जाँच करने के लिए हो सकता है यदि सूची पहले से ही सॉर्ट किया जाता है

84
00:04:10,520 --> 00:04:11,710
प्रत्येक यात्रा के बाद.

85
00:04:11,710 --> 00:04:13,900
यदि यह पहले से ही हल है, हम किसी भी अधिक पुनरावृत्तियों बनाने की जरूरत नहीं

86
00:04:13,900 --> 00:04:15,310
सूची के माध्यम से.

87
00:04:15,310 --> 00:04:16,220
हम यह कैसे कर सकते हैं?

88
00:04:16,220 --> 00:04:19,360
खैर, अगर हम किसी भी स्वैप एक सूची के माध्यम से गुजरती पर बनाना नहीं है,

89
00:04:19,360 --> 00:04:22,350
यह स्पष्ट है कि सूची में पहले से ही है क्योंकि हम कुछ भी नहीं स्वैप किया हल किया गया था.

90
00:04:22,350 --> 00:04:24,160
तो हम निश्चित रूप से फिर तरह नहीं है.

91
00:04:24,160 --> 00:04:27,960
>> शायद तुम एक झंडा चर 'हल नहीं' नामक शुरू नहीं कर पाया

92
00:04:27,960 --> 00:04:30,990
झूठी और यह सच में बदलने के लिए अगर आप पर किसी भी तत्व को स्वैप

93
00:04:30,990 --> 00:04:32,290
सरणी के माध्यम से एक चलना.

94
00:04:32,290 --> 00:04:35,350
या इसी तरह, एक काउंटर बनाने के लिए गिनती के लिए कितने स्वैप आप बनाने

95
00:04:35,350 --> 00:04:37,040
किसी भी यात्रा पर.

96
00:04:37,040 --> 00:04:40,040
एक चलना के अंत में, अगर आप तत्वों की किसी भी स्वैप नहीं था,

97
00:04:40,040 --> 00:04:41,780
आप जानते हैं कि सूची पहले से ही हल है और आप कर रहे हैं.

98
00:04:41,780 --> 00:04:44,090
बुलबुला तरह, अन्य छँटाई एल्गोरिदम की तरह हो सकता है,

99
00:04:44,090 --> 00:04:46,960
किसी भी तत्व है जो एक आदेश विधि के लिए काम करने के लिए tweaked.

100
00:04:46,960 --> 00:04:50,610
>> कि दो तत्वों दिया आप कहने के लिए एक तरीका है, अगर पहले एक

101
00:04:50,610 --> 00:04:53,770
की तुलना में, दूसरे से कम के बराबर या अधिक से अधिक है.

102
00:04:53,770 --> 00:04:56,870
उदाहरण के लिए, आप कह रही द्वारा वर्णमाला के अक्षर की तरह सकता है

103
00:04:56,870 --> 00:05:00,520
कि एक <ख, ख <सी, आदि,

104
00:05:00,520 --> 00:05:03,830
या आप सप्ताह के दिनों में ऐसी जगह है जहां रविवार सोमवार की तुलना में कम हो सकता है हो सकता है

105
00:05:03,830 --> 00:05:05,110
जो मंगलवार की तुलना में कम है.

106
00:05:05,110 --> 00:05:09,630
>> बुलबुला तरह कोई एक बहुत ही कुशल है या तेजी से छँटाई एल्गोरिथ्म का मतलब है.

107
00:05:09,630 --> 00:05:12,370
इसके सबसे ज्यादा मामले क्रम n बड़ी हे ² है

108
00:05:12,370 --> 00:05:14,810
क्योंकि आप एक सूची के माध्यम से n पुनरावृत्तियों करना है

109
00:05:14,810 --> 00:05:18,430
सभी n तत्वों की जाँच के माध्यम से प्रत्येक पारित करने के लिए, nxn n = ².

110
00:05:18,430 --> 00:05:22,730
इस चलाने के लिए समय का मतलब है कि तत्वों की संख्या के रूप में बढ़ जाती है छँटाई कर रहे हैं,

111
00:05:22,730 --> 00:05:24,330
चलाते समय quadratically बढ़ जाती है.

112
00:05:24,330 --> 00:05:27,330
>> लेकिन अगर क्षमता अपने कार्यक्रम के एक प्रमुख चिंता का विषय नहीं है

113
00:05:27,330 --> 00:05:29,550
या यदि आप केवल तत्वों की एक छोटी संख्या छँटाई कर रहे हैं,

114
00:05:29,550 --> 00:05:31,660
आप बुलबुला तरह उपयोगी मिल सकता है क्योंकि

115
00:05:31,660 --> 00:05:33,360
यह एक सरल छँटाई एल्गोरिदम की है समझने के लिए

116
00:05:33,360 --> 00:05:34,250
कोड और.

117
00:05:34,250 --> 00:05:37,270
यह भी एक शानदार तरीका है करने के लिए एक सैद्धांतिक अनुवाद के साथ अनुभव प्राप्त

118
00:05:37,270 --> 00:05:40,220
वास्तविक कार्य कोड में एल्गोरिथ्म.

119
00:05:40,220 --> 00:05:43,000
खैर, कि आप के लिए बुलबुला तरह है. देखने के लिए धन्यवाद.

120
00:05:43,000 --> 00:05:44,000
CS50.TV