1
00:00:06,762 --> 00:00:09,980
[Powered by Google Translate] טומי: בואו נסתכל על מיון בחירה, אלגוריתם

2
00:00:09,980 --> 00:00:12,800
לקחת רשימה של מספרים ומיונם.

3
00:00:12,800 --> 00:00:15,750
אלגוריתם, לזכור, הוא פשוט צעד אחר צעד

4
00:00:15,750 --> 00:00:18,370
הליך להשגת משימה.

5
00:00:18,370 --> 00:00:21,470
הרעיון הבסיסי מאחורי מיון בחירה הוא לחלק את

6
00:00:21,470 --> 00:00:23,390
הרשימה שלנו לשני חלקים -

7
00:00:23,390 --> 00:00:26,810
חלק ממוין וחלק לא ממוין.

8
00:00:26,810 --> 00:00:30,200
בכל צעד של האלגוריתם, מספר מועבר מ

9
00:00:30,200 --> 00:00:33,800
חלק ממוין לחלק מסודר עד סופו של הדבר

10
00:00:33,800 --> 00:00:35,880
כל הרשימה ממוינת.

11
00:00:35,880 --> 00:00:38,510
אז הנה רשימה של שישה מספרים -

12
00:00:38,510 --> 00:00:44,010
23, 42, 4, 16, 8, ו 15.

13
00:00:44,010 --> 00:00:47,680
נכון לעכשיו כל הרשימה נחשבת ללא מיון.

14
00:00:47,680 --> 00:00:51,770
למרות מספר כמו 16 מאי כבר יהיה בנכון

15
00:00:51,770 --> 00:00:56,040
מיקום, האלגוריתם שלנו אין דרך לדעת שעד

16
00:00:56,040 --> 00:00:57,980
כל הרשימה ממוינת.

17
00:00:57,980 --> 00:01:01,355
כך יהיה לנו לשקול כל מספר שיש המיון, עד שנמיין

18
00:01:01,355 --> 00:01:03,800
זה בעצמנו.

19
00:01:03,800 --> 00:01:06,890
אנחנו יודעים שאנחנו רוצים את הרשימה כדי להיות בסדר עולה.

20
00:01:06,890 --> 00:01:10,200
אז אנחנו רוצים לבנות את החלק הממוין של הרשימה שלנו

21
00:01:10,200 --> 00:01:13,280
משמאל לימין, הקטן ביותר לגדול ביותר.

22
00:01:13,280 --> 00:01:17,970
כדי לעשות זאת, יצטרך למצוא את האלמנט הממוין המינימום

23
00:01:17,970 --> 00:01:21,350
ולשים אותו בסוף החלק הממוין.

24
00:01:21,350 --> 00:01:25,370
מאז רשימה זו אינה ממוינת, הדרך היחידה לעשות זאת היא

25
00:01:25,370 --> 00:01:29,330
להסתכל על כל אלמנט בחלק הממוין, נזכר

26
00:01:29,330 --> 00:01:32,010
איזה רכיב הוא נמוך ביותר ומשווה

27
00:01:32,010 --> 00:01:33,770
כל רכיב לזה.

28
00:01:33,770 --> 00:01:36,150
כך יהיה לנו קודם להסתכל 23.

29
00:01:36,150 --> 00:01:38,650
זהו היסוד הראשון שראינו, ולכן אנחנו זוכרים

30
00:01:38,650 --> 00:01:40,050
זה כמינימום.

31
00:01:40,050 --> 00:01:42,320
כעת נדון בגיל 42.

32
00:01:42,320 --> 00:01:46,720
42 הם גדולים יותר מאשר 23, ולכן 23 הם עדיין מזעריים.

33
00:01:46,720 --> 00:01:51,210
הבא הוא 4 שהם פחות מ 23, ולכן אנחנו זוכרים 4

34
00:01:51,210 --> 00:01:52,880
כמינימום החדש.

35
00:01:52,880 --> 00:01:56,380
הבא הוא 16 שהוא גדול יותר מ 4, אז 4

36
00:01:56,380 --> 00:01:57,980
עדיין המינימום.

37
00:01:57,980 --> 00:02:03,670
8 הן גדולים יותר מאשר 4, ו 15 הן גדולים יותר מאשר 4, ולכן 4 חייבות להיות

38
00:02:03,670 --> 00:02:05,980
האלמנט הקטן ביותר הממוין.

39
00:02:05,980 --> 00:02:09,350
אז למרות שכבני אדם אנחנו יכולים לראות מייד ש4 הם

40
00:02:09,350 --> 00:02:12,300
האלמנט המינימאלי, האלגוריתם שלנו צריך להסתכל על

41
00:02:12,300 --> 00:02:15,710
כל אלמנט לא ממוין, גם לאחר שמצאנו את 4 -

42
00:02:15,710 --> 00:02:16,860
אלמנט מינימום.

43
00:02:16,860 --> 00:02:19,900
אז עכשיו שמצאנו את האלמנט המינימאלי, 4, אנחנו רוצים

44
00:02:19,900 --> 00:02:23,410
כדי להעביר אותו לחלק הממוין של הרשימה.

45
00:02:23,410 --> 00:02:27,320
מכיוון שזו היא הצעד הראשון, זה אומר שאנחנו רוצים לשים ב4

46
00:02:27,320 --> 00:02:29,680
תחילת הרשימה.

47
00:02:29,680 --> 00:02:33,040
נכון לעכשיו 23 הם בתחילת הרשימה, כך

48
00:02:33,040 --> 00:02:36,080
בואו להחליף 4 ו 23.

49
00:02:36,080 --> 00:02:38,870
אז עכשיו הרשימה שלנו נראית כך.

50
00:02:38,870 --> 00:02:42,710
אנו יודעים כי 4 חייבים להיות במיקומה הסופי, משום שהוא

51
00:02:42,710 --> 00:02:45,890
גם האלמנט הקטן ביותר והאלמנט בתחילה

52
00:02:45,890 --> 00:02:46,960
מהרשימה.

53
00:02:46,960 --> 00:02:50,650
אז זה אומר שאנחנו אף פעם לא נצטרך לעבור את זה שוב.

54
00:02:50,650 --> 00:02:53,910
אז בואו נחזור על תהליך זה כדי להוסיף אלמנט נוסף

55
00:02:53,910 --> 00:02:55,910
חלק ממוין של הרשימה.

56
00:02:55,910 --> 00:02:58,950
אנחנו יודעים שאנחנו לא צריכים להסתכל על 4, כי זה

57
00:02:58,950 --> 00:03:00,000
כבר ממוין.

58
00:03:00,000 --> 00:03:03,540
אז אנחנו יכולים להתחיל ב42, שאנו נזכור כ

59
00:03:03,540 --> 00:03:05,290
אלמנט מינימום.

60
00:03:05,290 --> 00:03:08,700
אז הבא שנסתכל על 23 שהם פחות מ 42, ולכן אנחנו

61
00:03:08,700 --> 00:03:11,620
זוכר את 23 הוא המינימום החדש.

62
00:03:11,620 --> 00:03:14,870
הבא אנו רואים 16 שהן פחות מ 23, ולכן

63
00:03:14,870 --> 00:03:16,800
16 הם המינימום החדש.

64
00:03:16,800 --> 00:03:19,720
עכשיו אנחנו מסתכלים על 8 שהם פחות מ 16, ולכן

65
00:03:19,720 --> 00:03:21,130
8 הם המינימום החדש.

66
00:03:21,130 --> 00:03:25,900
ולבסוף 8 הם פחות מ 15, כך אנו יודעים כי 8 הם מינימום

67
00:03:25,900 --> 00:03:27,780
אלמנט לא ממוין.

68
00:03:27,780 --> 00:03:30,660
אז זה אומר שאנחנו צריכים לצרף 8 למיון

69
00:03:30,660 --> 00:03:32,450
חלק מהרשימה.

70
00:03:32,450 --> 00:03:35,990
כרגע 4 הם האלמנט מסודר בלבד, ולכן אנחנו רוצים למקם

71
00:03:35,990 --> 00:03:38,410
8 לצד 4.

72
00:03:38,410 --> 00:03:41,920
מאז 42 הוא האלמנט הראשון בחלק הממוין של

73
00:03:41,920 --> 00:03:47,260
רשימה, אנחנו רוצים להחליף 42 ו 8.

74
00:03:47,260 --> 00:03:49,680
אז עכשיו הרשימה שלנו נראית כך.

75
00:03:49,680 --> 00:03:53,830
4 ל 8 מייצגים את החלק הממוין של הרשימה, ו

76
00:03:53,830 --> 00:03:56,440
מספרים שנותרו לייצג הממוינים

77
00:03:56,440 --> 00:03:58,260
חלק מהרשימה.

78
00:03:58,260 --> 00:04:00,630
אז בואו נמשיך עם איטרציה אחרת.

79
00:04:00,630 --> 00:04:03,850
אנחנו מתחילים עם 23 הפעם, מכיוון שאנחנו לא צריכים להסתכל על

80
00:04:03,850 --> 00:04:05,770
4 ו 8 יותר, כי יש להם

81
00:04:05,770 --> 00:04:07,660
כבר ממוין.

82
00:04:07,660 --> 00:04:10,270
16 הם פחות מ 23, ולכן אנחנו זוכרים

83
00:04:10,270 --> 00:04:12,070
16 כמינימום החדש.

84
00:04:12,070 --> 00:04:18,149
16 הם פחות מ 42, אבל 15 הוא פחות מ 16, ולכן חייבים להיות 15

85
00:04:18,149 --> 00:04:20,480
האלמנט הממוין המינימום.

86
00:04:20,480 --> 00:04:24,580
אז עכשיו אנחנו רוצים להחליף 15 ו 23 ל

87
00:04:24,580 --> 00:04:26,310
לתת לנו את הרשימה הזאת.

88
00:04:26,310 --> 00:04:30,500
החלק הממוין של הרשימה מורכבת מ4, 8 ו 15, ו

89
00:04:30,500 --> 00:04:33,210
אלמנטים אלה עדיין לא ממוינים.

90
00:04:33,210 --> 00:04:36,900
אבל זה פשוט כל כך קורה כי האלמנט הבא לא ממוין, 16,

91
00:04:36,900 --> 00:04:38,480
כבר ממוין.

92
00:04:38,480 --> 00:04:42,060
עם זאת, אין דרך לאלגוריתם שלנו לדעת כי 16

93
00:04:42,060 --> 00:04:45,230
כבר במיקום הנכון שלו, ולכן אנחנו עדיין צריכים

94
00:04:45,230 --> 00:04:47,870
חוזר בדיוק על אותו התהליך.

95
00:04:47,870 --> 00:04:53,750
כך אנו רואים כי 16 הם פחות מ 42, ו 16 הוא פחות מ 23, ולכן

96
00:04:53,750 --> 00:04:56,230
16 חייבים להיות אלמנט המינימום.

97
00:04:56,230 --> 00:04:59,010
אי אפשר להחליף את האלמנט הזה בעצמו, כדי שנוכל

98
00:04:59,010 --> 00:05:01,780
פשוט להשאיר אותו במיקום זה.

99
00:05:01,780 --> 00:05:04,660
אז אנחנו צריכים עוד אחד של האלגוריתם שלנו עוברים.

100
00:05:04,660 --> 00:05:09,370
42 גדולים מ 23, ולכן חייבים להיות 23

101
00:05:09,370 --> 00:05:10,970
אלמנט ממוין מינימום.

102
00:05:10,970 --> 00:05:17,410
ברגע שאנו מחליפים 23 ו 42, אנחנו בסופו של דבר עימנו סופי

103
00:05:17,410 --> 00:05:18,530
רשימה ממוינת -

104
00:05:18,530 --> 00:05:23,390
4, 8, 15, 16, 23, 42.

105
00:05:23,390 --> 00:05:26,830
אנחנו יודעים 42 חייבים להיות במקום הנכון, מכיוון שזה

106
00:05:26,830 --> 00:05:30,210
אלמנט היחיד שנותר, וזה מיון בחירה.

107
00:05:30,210 --> 00:05:32,100
בואו עכשיו למסד האלגוריתם שלנו עם כמה

108
00:05:32,100 --> 00:05:34,540
pseudocode.

109
00:05:34,540 --> 00:05:37,760
בשורה אחת, אנו יכולים לראות שאנחנו צריכים לשלב יותר

110
00:05:37,760 --> 00:05:39,530
כל אלמנט של הרשימה.

111
00:05:39,530 --> 00:05:42,150
מלבד האלמנט האחרון, מאז היסוד 1

112
00:05:42,150 --> 00:05:44,230
רשימה כבר ממוינת.

113
00:05:44,230 --> 00:05:48,100
על קו 2, אנו רואים במרכיב הראשון של ממוין

114
00:05:48,100 --> 00:05:51,080
חלק מהרשימה כדי להיות המינימום, כפי שעשינו עימנו

115
00:05:51,080 --> 00:05:53,750
למשל, אז יש לנו מה להשוות.

116
00:05:53,750 --> 00:05:57,260
קו 3 מתחיל לולאה שנייה בה אנו לחזר על

117
00:05:57,260 --> 00:05:59,170
כל רכיב לא ממוין.

118
00:05:59,170 --> 00:06:02,150
אנחנו יודעים שאחרי שחזרות, החלק מסודר

119
00:06:02,150 --> 00:06:05,330
הרשימה שלנו חייב להיות i אלמנטים בזה מאז כל צעד

120
00:06:05,330 --> 00:06:06,890
מיני אלמנט אחד.

121
00:06:06,890 --> 00:06:11,770
אז האלמנט הממוין הראשון חייב להיות בעמדתי ועוד 1.

122
00:06:11,770 --> 00:06:15,440
על קו 4, אנו משווים את האלמנט הנוכחי למינימום

123
00:06:15,440 --> 00:06:17,750
אלמנט שראינו עד כה.

124
00:06:17,750 --> 00:06:20,560
אם הרכיב הנוכחי הוא קטן יותר מהמינימום

125
00:06:20,560 --> 00:06:23,870
אלמנט, אז אנחנו זוכרים את האלמנט הנוכחי כחדשים

126
00:06:23,870 --> 00:06:26,250
מינימום על קו 5.

127
00:06:26,250 --> 00:06:29,900
לבסוף, על קווים שישה ושבעה, אנחנו מחליפים את המינימום

128
00:06:29,900 --> 00:06:33,080
אלמנט עם האלמנט הממוין הראשון, ובכך

129
00:06:33,080 --> 00:06:36,990
הוספתו לחלק הממוין של הרשימה.

130
00:06:36,990 --> 00:06:40,030
ברגע שיש לנו אלגוריתם, שאלה חשובה לשאול

131
00:06:40,030 --> 00:06:43,370
את עצמנו כמו מתכנתים הם כמה זמן זה ייקח?

132
00:06:43,370 --> 00:06:46,970
נשאלים את השאלה הראשונה כמה זמן לוקח לזה

133
00:06:46,970 --> 00:06:50,070
אלגוריתם לרוץ במקרה הגרוע ביותר?

134
00:06:50,070 --> 00:06:51,640
זוכרים שאנחנו מייצגים את זה פועל

135
00:06:51,640 --> 00:06:55,060
זמן עם סימון O גדול.

136
00:06:55,060 --> 00:06:58,650
על מנת לקבוע את האלמנט הממוין המינימום, אנחנו

137
00:06:58,650 --> 00:07:01,880
למעשה הייתי צריך להשוות כל רכיב ברשימה כדי

138
00:07:01,880 --> 00:07:04,040
כל אלמנט אחר ברשימה.

139
00:07:04,040 --> 00:07:08,430
באופן אינטואיטיבי, זה נשמע כמו O של מבצע ריבוע n.

140
00:07:08,430 --> 00:07:12,050
כאשר מסתכלים על pseudocode שלנו, יש לנו גם מקוננת בתוך לולאה

141
00:07:12,050 --> 00:07:14,420
עוד לולאה, שאכן נשמעת כמו O

142
00:07:14,420 --> 00:07:16,480
פעולת ריבוע n.

143
00:07:16,480 --> 00:07:19,250
עם זאת, יש לזכור שאנחנו לא צריכים להסתכל על

144
00:07:19,250 --> 00:07:23,460
כל רשימה בעת קביעת המרכיב הממוין המינימום?

145
00:07:23,460 --> 00:07:26,600
ברגע שידענו ש4 מוינו, למשל, לא אצלנו

146
00:07:26,600 --> 00:07:28,170
צריך להסתכל על זה שוב.

147
00:07:28,170 --> 00:07:31,020
אז עושה את זה נמוך זמן הריצה?

148
00:07:31,020 --> 00:07:34,510
לרשימה של 6 אורך שלנו, אנחנו צריכים לעשות 5

149
00:07:34,510 --> 00:07:37,990
השוואות לאלמנט הראשון, ארבעה להשוואות

150
00:07:37,990 --> 00:07:40,750
האלמנט השני, וכן הלאה.

151
00:07:40,750 --> 00:07:44,690
זה אומר שהמספר הכולל של צעדים הוא הסכום של

152
00:07:44,690 --> 00:07:49,160
המספרים השלמים מ 1 עד האורך של רשימת מינוס 1.

153
00:07:49,160 --> 00:07:51,005
אנו יכולים לציין זאת בסיכום.

154
00:07:57,980 --> 00:07:59,910
אנחנו לא נכנסנו לסיכומים לכאן.

155
00:07:59,910 --> 00:08:04,900
אבל מתברר שסיכום זה שווה לפעמי n

156
00:08:04,900 --> 00:08:07,540
n מינוס 1 מעל 2.

157
00:08:07,540 --> 00:08:14,220
או באופן שקול, n בריבוע מעל 2 מינוס n מעל 2.

158
00:08:14,220 --> 00:08:18,860
כאשר מדברים על זמן ריצת אסימפטוטי, מונח בריבוע זה n

159
00:08:18,860 --> 00:08:22,070
הולך לשלוט טווח n זה.

160
00:08:22,070 --> 00:08:27,850
אז מיון בחירה הוא O של n בריבוע.

161
00:08:27,850 --> 00:08:31,460
כזכור, בדוגמא שלנו, מיון בחירה עדיין צריך

162
00:08:31,460 --> 00:08:33,850
לבדוק אם מספר שכבר מסודר

163
00:08:33,850 --> 00:08:35,450
צורך להתרגש.

164
00:08:35,450 --> 00:08:38,929
אז זה אומר שאם רץ מיון בחירה מעל כבר

165
00:08:38,929 --> 00:08:43,070
מסודר על רשימה, זה ידרוש את אותו המספר של צעדים כמו זה

166
00:08:43,070 --> 00:08:46,340
היית כאשר פועלים על רשימה לחלוטין לא ממוינת.

167
00:08:46,340 --> 00:08:51,470
אז מיון בחירה יש מקרה ביצועים טובים ביותר של n בריבוע,

168
00:08:51,470 --> 00:08:56,820
שאנו מייצגים עם אומגת n בריבוע.

169
00:08:56,820 --> 00:08:58,600
וזהו זה למיון בחירה.

170
00:08:58,600 --> 00:09:00,630
זהו רק אחד מהאלגוריתמים הרבים אנו יכולים

171
00:09:00,630 --> 00:09:02,390
להשתמש כדי למיין רשימה.

172
00:09:02,390 --> 00:09:05,910
השמי הוא טומי, וזה cs50.