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 اگر آن را در حال حاضر 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،
بزرگترین ارزش، تمام راه را به پایان است.

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
بنابراین ما با 2 شروع و 1-- آنها
خارج از دستور، بنابراین ما آنها را مبادله

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
اما ضد مبادله است که هنوز هم 0.

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
تمام راه در سراسر آرایه، TOO.

113
00:04:57,050 --> 00:05:01,950
بنابراین هر یک از عناصر نفر به حرکت
در سراسر همه از دیگر عناصر 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 بار.

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
و اگر شمارنده مبادله است که هنوز هم 0،
شما می توانید می گویند این آرایه مرتب شده اند.

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