1
00:00:00,000 --> 00:00:05,726
>> [השמעת מוסיקה]

2
00:00:05,726 --> 00:00:08,600
דאג LLOYD: סוג הבחירה הוא
אלגוריתם ש, כפי שאתה יכול לצפות,

3
00:00:08,600 --> 00:00:10,470
ממיין סט של אלמנטים.

4
00:00:10,470 --> 00:00:12,470
וזוכר אלגוריתם
היא קבוצת צעד-אחר-צעד

5
00:00:12,470 --> 00:00:15,260
הוראות להשלמת משימה.

6
00:00:15,260 --> 00:00:17,580
>> בבחירה למיין
רעיון בסיסי הוא זה,

7
00:00:17,580 --> 00:00:22,080
למצוא את האלמנט ממוין הקטן ו
להוסיף אותו לסוף הרשימה הממוינת.

8
00:00:22,080 --> 00:00:26,970
יעילות מה המשמעות של זה הוא לבנות
רשימה ממוינת, אלמנט אחד בכל פעם.

9
00:00:26,970 --> 00:00:29,800
הפירוק לפסאודו קוד
אנחנו יכולים לומר אלגוריתם זה

10
00:00:29,800 --> 00:00:34,490
כדלקמן, לחזור על זה עד ש
אין אלמנטים ממוינים להישאר.

11
00:00:34,490 --> 00:00:38,660
חיפוש דרך לא ממוינים
נתונים כדי למצוא את הערך הקטן ביותר,

12
00:00:38,660 --> 00:00:44,130
לאחר מכן להחליף את הערך הקטן ביותר עם
האלמנט הראשון של חלק לא ממוינים.

13
00:00:44,130 --> 00:00:47,130
>> זה עשוי לעזור כדי להמחיש את זה,
אז בואו נסתכל על זה.

14
00:00:47,130 --> 00:00:49,710
אז זה, אני טוען, הוא
ומערך לא ממוינים לי

15
00:00:49,710 --> 00:00:53,040
הצביע אותו על ידי המצביע על כך כל
של האלמנטים בצבע אדום,

16
00:00:53,040 --> 00:00:54,420
הם עדיין לא מסודרים.

17
00:00:54,420 --> 00:00:57,670
זה כל
חלק לא ממוינים של המערך.

18
00:00:57,670 --> 00:01:02,020
>> אז בואו לעבור את השלבים של
מיון בחירה למיין מערך זה.

19
00:01:02,020 --> 00:01:05,296
אז שוב, אנחנו חוזרים הולכים
עד שלא יישארו אלמנטים לא ממוינים.

20
00:01:05,296 --> 00:01:07,920
אנחנו הולכים דרך חיפוש
נתונים כדי למצוא את הערך הקטן ביותר,

21
00:01:07,920 --> 00:01:11,990
ולאחר מכן להחליף ערך שעם
האלמנט הראשון של חלק לא ממוינים.

22
00:01:11,990 --> 00:01:14,380
>> עכשיו, שוב, כל
מערך הוא החלק ממוין.

23
00:01:14,380 --> 00:01:16,534
כל האלמנטים האדומים הם לא ממוינים.

24
00:01:16,534 --> 00:01:18,700
אז אנו מחפשים דרך ו
אנו מוצאים את הערך הקטן ביותר.

25
00:01:18,700 --> 00:01:20,533
אנחנו מתחילים בתחילת,
אנחנו הולכים עד הסוף,

26
00:01:20,533 --> 00:01:23,630
אנו מוצאים את הערך הקטן ביותר הוא, אחת.

27
00:01:23,630 --> 00:01:24,860
אז זה חלק אחד.

28
00:01:24,860 --> 00:01:29,440
ואז חלק שני, להחליף ערך שעם
האלמנט הראשון של חלק לא ממוינים,

29
00:01:29,440 --> 00:01:31,340
או האלמנט האדום הראשון.

30
00:01:31,340 --> 00:01:34,980
>> במקרה זה שיהיה
חמש, ולכן אנחנו להחליף אחד וחמש.

31
00:01:34,980 --> 00:01:37,320
כאשר אנו עושים זאת, אנחנו יכולים
מבחינה ויזואלית לראות שיש לנו

32
00:01:37,320 --> 00:01:41,260
עבר האלמנט המוערך הקטן ביותר
של המערך, להתחלה.

33
00:01:41,260 --> 00:01:43,920
יעילות מיון אלמנט ש.

34
00:01:43,920 --> 00:01:47,520
>> וכך אנו יכולים לאשר אכן
ומדינה שאחד, ממוין.

35
00:01:47,520 --> 00:01:52,080
וכך אנו מציינים את החלק מסודרים
של המערך שלנו, על ידי צביעתו כחולה.

36
00:01:52,080 --> 00:01:53,860
>> עכשיו אנחנו רק לחזור על התהליך שוב.

37
00:01:53,860 --> 00:01:57,430
אנחנו מחפשים דרך החלק ממוין של
המערך למצוא את האלמנט הקטן ביותר.

38
00:01:57,430 --> 00:01:59,000
במקרה זה, זה שתי.

39
00:01:59,000 --> 00:02:02,100
>> אנו להחליף את זה עם ראשון
אלמנט של חלק לא ממוינים.

40
00:02:02,100 --> 00:02:05,540
במקרה זה שני גם במקרה
האלמנט הראשון של חלק לא ממוינים.

41
00:02:05,540 --> 00:02:08,650
אז אנחנו להחליף שתי עם עצמו,
שבאמת רק משאיר שני

42
00:02:08,650 --> 00:02:11,257
איפה זה, וזה מסודרים.

43
00:02:11,257 --> 00:02:13,840
ממשיך ב, אנו מחפשים דרך
כדי למצוא את האלמנט הקטן ביותר.

44
00:02:13,840 --> 00:02:15,030
זה שלוש.

45
00:02:15,030 --> 00:02:17,650
אנחנו להחליף אותו עם הראשון
אלמנט, שהוא חמש.

46
00:02:17,650 --> 00:02:19,450
ועכשיו שלוש ממוין.

47
00:02:19,450 --> 00:02:22,440
>> אנחנו מחפשים דרך שוב, ואנחנו
למצוא את האלמנט הקטן ביותר הוא ארבעה.

48
00:02:22,440 --> 00:02:28,070
אנחנו להחליף אותו עם האלמנט הראשון של
חלק לא ממוינים, ועכשיו ארבעה ממוינים.

49
00:02:28,070 --> 00:02:29,910
>> אנו מוצאים כי חמישה הוא
האלמנט הקטן ביותר.

50
00:02:29,910 --> 00:02:32,900
אנחנו להחליף אותו עם הראשון
אלמנט של חלק לא ממוינים.

51
00:02:32,900 --> 00:02:34,740
ועכשיו חמש ממוין.

52
00:02:34,740 --> 00:02:36,660
>> ואז לבסוף,
חלק ממוין מורכב

53
00:02:36,660 --> 00:02:38,576
רק אלמנט אחד,
כך אנו מחפשים דרך

54
00:02:38,576 --> 00:02:41,740
ואנו מוצאים כי שישה הוא
הקטן ביותר, ולמעשה, רק האלמנט.

55
00:02:41,740 --> 00:02:44,906
ואז אנחנו יכולים לומר שהוא מסודרים.

56
00:02:44,906 --> 00:02:47,530
ועכשיו אנחנו כבר עברנו המערך שלנו
מלהיות ממוין לחלוטין

57
00:02:47,530 --> 00:02:52,660
באדום, למסודר לגמרי
בכחול, באמצעות מיון בחירה.

58
00:02:52,660 --> 00:02:54,920
>> אז מה התרחיש הגרוע ביותר כאן?

59
00:02:54,920 --> 00:02:57,830
ובכן במוחלט הגרוע ביותר
מקרה, אנחנו צריכים להסתכל על

60
00:02:57,830 --> 00:03:02,170
כל האלמנטים של המערך ל
למצוא את האלמנט ממוין הקטן ביותר,

61
00:03:02,170 --> 00:03:04,750
ואנחנו צריכים לחזור
תהליך זה n פעמים.

62
00:03:04,750 --> 00:03:09,090
פעם אחת עבור כל אלמנט של המערך
כי אנחנו היחידים, באלגוריתם זה,

63
00:03:09,090 --> 00:03:12,180
סוג אלמנט אחד בכל פעם.

64
00:03:12,180 --> 00:03:13,595
>> מה התרחיש הטוב ביותר?

65
00:03:13,595 --> 00:03:15,040
ובכן זה בדיוק אותו הדבר, נכון?

66
00:03:15,040 --> 00:03:18,440
אנחנו באמת צריכים עדיין לצעד דרך
כל אלמנט של המערך

67
00:03:18,440 --> 00:03:22,040
כדי לאשר שזה,
למעשה, האלמנט הקטן ביותר.

68
00:03:22,040 --> 00:03:26,760
>> אז במקרה הגרוע ביותר של זמן הריצה, אנחנו
יש לחזור על תהליך n פעמים,

69
00:03:26,760 --> 00:03:28,960
פעם אחת לכל אחד מאלמנטי n.

70
00:03:28,960 --> 00:03:31,940
ובמקרה הטוב,
אנחנו צריכים לעשות את אותו הדבר.

71
00:03:31,940 --> 00:03:35,340
>> אז חשבתי לחזור לנו
ארגז כלים מורכבות חישובית,

72
00:03:35,340 --> 00:03:39,250
מה אתה חושב הוא הגרוע ביותר
מקרה ריצה למיון בחירה?

73
00:03:39,250 --> 00:03:41,840
מה אתה חושב הוא הטוב ביותר
מקרה ריצה למיון בחירה?

74
00:03:41,840 --> 00:03:44,760

75
00:03:44,760 --> 00:03:49,325
>> האם אתה מניח Big O של n בריבוע,
ואומגה הגדולה של n בריבוע?

76
00:03:49,325 --> 00:03:49,950
אתה רוצה להיות תקין.

77
00:03:49,950 --> 00:03:52,490
אלה הם, למעשה,
במקרה הגרוע ביותר ומקרה הטוב ביותר לרוץ

78
00:03:52,490 --> 00:03:55,100
פעמים, למיון בחירה.

79
00:03:55,100 --> 00:03:56,260
>> אני דאג לויד.

80
00:03:56,260 --> 00:03:58,600
זה CS50.

81
00:03:58,600 --> 00:04:00,279