1
00:00:00,500 --> 00:00:02,840
[Powered by Google Translate] [מיון בועות]

2
00:00:02,840 --> 00:00:04,560
[JACKSON 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
הם - 3 גדולים מ 2.

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
לבסוף, אנחנו מסתכלים על שני מספרים השלמים האחרון, 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, 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
אז זה לוקח מספר Pass-throughs שווה למספר

46
00:02:17,840 --> 00:02:19,730
אלמנטים של n-1.

47
00:02:19,730 --> 00:02:24,720
אם זה לא הגיוני באופן אינטואיטיבי, חושב על מקרה פשוט - הרשימה [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
>> אחרי חזרות מ 'דרך כל המערך,

59
00:02:57,410 --> 00:02:59,000
האלמנטים מ 'הימניים ביותר מובטחים

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, 3, 2], [6, 5, 9, 3, 2], [6, 5, 3, 9, 2], [6, 5, 3, 2, 9]

66
00:03:18,790 --> 00:03:21,250
האלמנט הימני ביותר הוא 9 במקום הראוי לו.

67
00:03:21,250 --> 00:03:24,760
לאחר 2 תמסורת, 6 יהיו 'בעבע למעלה "כדי

68
00:03:24,760 --> 00:03:26,220
מקום הימני ביותר 2.

69
00:03:26,220 --> 00:03:28,840
שני האלמנטים בימין - 6 ו 9 - יהיו במקומות הנכונים

70
00:03:28,840 --> 00:03:30,580
אחרי שני Pass-throughs 1.

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
אנחנו לא באמת צריכים לבדוק את המרכיב הימני ביותר

74
00:03:37,690 --> 00:03:39,200
כי אנחנו יודעים שזה מסודר.

75
00:03:39,200 --> 00:03:43,050
לאחר שתי חזרות, אנחנו יודעים בודאות את שני אלמנטים הימניים ביותר נמצאים במקום.

76
00:03:43,050 --> 00:03:48,260
אז, באופן כללי, לאחר חזרות k באמצעות מערך המלא,

77
00:03:48,260 --> 00:03:51,550
בדיקת אלמנטי k האחרונים היא מיותר מכיוון שאנו יודעים

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
בגרסה הראשונה - תכף צריכה למיין את כל האלמנטים - n-0 1.

81
00:03:57,870 --> 00:04:04,170
על החזרה השנייה, אתה צריך להסתכל על כל האלמנטים אבל אחרון -

82
00:04:04,170 --> 00:04:07,090
1 n-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
צבט לעבוד עבור כל רכיבים שיש להם שיטת הזמנה.

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
ש< B, B <ג, וכו '

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
המקרה הגרוע ביותר זמן הריצה שלו הוא ביג O של 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