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
דאג LLOYD: בסדר, כל כך
מיון בועות הוא אלגוריתם

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
אז שוב, הצעדים הן--
לאפס את מונה ההחלפה

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
כל הדרך על פני המערך, מדי.

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
ואם דלפק ההחלפה הוא עדיין 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