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

2
00:00:02,826 --> 00:00:05,660

3
00:00:05,660 --> 00:00:09,370
>> דאג LLOYD: אז מיון ההכנסה הוא עוד
אלגוריתם שאנחנו יכולים להשתמש בו כדי למיין את המערך.

4
00:00:09,370 --> 00:00:12,350
הרעיון מאחורי אלגוריתם זה
הוא לבנות מערך המיון שלך

5
00:00:12,350 --> 00:00:19,670
במקום, הסטת אלמנטים מתוך
הדרך כמו שאתה הולך, כדי לפנות מקום.

6
00:00:19,670 --> 00:00:22,240
זה שונה במקצת
מסוג הבחירה או בועה

7
00:00:22,240 --> 00:00:25,460
סוג, לדוגמא, שבו
אנחנו התאמת המקומות,

8
00:00:25,460 --> 00:00:26,910
שבו אנחנו עושים חילופים.

9
00:00:26,910 --> 00:00:29,760
>> במקרה זה מה שאנחנו בעצם
עושים הוא אלמנטים זזים

10
00:00:29,760 --> 00:00:31,390
מעל, מהדרך.

11
00:00:31,390 --> 00:00:34,030
כיצד אלגוריתם זה
לעבוד בפסאודו קוד?

12
00:00:34,030 --> 00:00:37,646
ובכן בואו רק באופן שרירותי אומר ש
האלמנט הראשון של המערך ממוין.

13
00:00:37,646 --> 00:00:38,770
אנחנו בונים אותו במקום.

14
00:00:38,770 --> 00:00:42,660
>> אנו אתה הולך ללכת אלמנט אחד בכל פעם ו
לבנות אותו, ולכן הדבר הראשון שאנו רואים

15
00:00:42,660 --> 00:00:43,890
הוא מערך אלמנט אחד.

16
00:00:43,890 --> 00:00:47,720
ועל ידי הגדרה, אחד
מערך אלמנט מסודרים.

17
00:00:47,720 --> 00:00:50,850
>> אז לחזור על תהליך זה until--
אנו לחזור על התהליך הבא

18
00:00:50,850 --> 00:00:52,900
עד שכל האלמנטים מסודרים.

19
00:00:52,900 --> 00:00:57,770
תסתכל על האלמנט ממוין הבא ו
הכנס אותו לחלק ממוין,

20
00:00:57,770 --> 00:01:01,209
על ידי העברת המספר הנדרש
אלמנטים מהדרך.

21
00:01:01,209 --> 00:01:03,750
אני מקווה שזה הדמיה
יעזור לך לראות בדיוק מה

22
00:01:03,750 --> 00:01:05,980
קורה עם מיון הכנסה.

23
00:01:05,980 --> 00:01:08,010
>> אז שוב, הנה
מערך לא ממוינים כל,

24
00:01:08,010 --> 00:01:10,970
כל האלמנטים שצוינו באדום.

25
00:01:10,970 --> 00:01:13,320
ובואו אחרי
צעדים של פסאודו הקוד שלנו.

26
00:01:13,320 --> 00:01:16,970
הדבר הראשון שאנחנו עושים, הוא שאנחנו קוראים
האלמנט הראשון של המערך, מסודרים.

27
00:01:16,970 --> 00:01:20,920
אז אנחנו רק נניח הולכים
חמש, אתה עכשיו מסודרים.

28
00:01:20,920 --> 00:01:24,570
>> ואז אנחנו מסתכל על הבאים
אלמנט לא ממוינים של המערך

29
00:01:24,570 --> 00:01:27,610
ואנחנו רוצים להכניס ש
לחלק מסודרים,

30
00:01:27,610 --> 00:01:29,750
על ידי העברת אלמנטים מעל.

31
00:01:29,750 --> 00:01:33,470
אז שני הוא לא ממוינים הבאים
אלמנט של המערך.

32
00:01:33,470 --> 00:01:36,250
ברור שהיא שייכת לפני
חמש, אז מה אנחנו הולכים לעשות

33
00:01:36,250 --> 00:01:41,580
הוא סוג של להחזיק שני בצד לרגע,
משמרת חמש מעל, ולאחר מכן להוסיף שני

34
00:01:41,580 --> 00:01:43,210
לפני חמש, איפה צריך ללכת.

35
00:01:43,210 --> 00:01:45,280
ועכשיו אנחנו יכולים לומר ששתי ממוינים.

36
00:01:45,280 --> 00:01:48,400
>> אז כפי שאתם יכולים לראות, יש לנו רק עד כה
הסתכל על שני אלמנטים של המערך.

37
00:01:48,400 --> 00:01:50,600
אנחנו לא נראים ב
לנוח בכל, אבל יש לנו

38
00:01:50,600 --> 00:01:54,582
יש שני אלמנטים אלה מסודרים על ידי
דרך של מנגנון ההסטה.

39
00:01:54,582 --> 00:01:56,410
>> אז אנחנו חוזרים על התהליך שוב.

40
00:01:56,410 --> 00:01:58,850
תסתכל על ממוין הבא
אלמנט, זה אחד.

41
00:01:58,850 --> 00:02:04,010
בואו להחזיק את זה בצד לרגע,
משמרת הכל נגמר, ולשים אחד

42
00:02:04,010 --> 00:02:05,570
איפה שהוא צריך ללכת.

43
00:02:05,570 --> 00:02:08,110
>> שוב, עדיין, יש לנו רק אי פעם
הסתכל אחד, שתי, וחמש.

44
00:02:08,110 --> 00:02:12,480
אנחנו לא יודעים מה עוד הוא מגיע,
אבל אנחנו כבר מסודרים שלושה האלמנטים האלה.

45
00:02:12,480 --> 00:02:16,030
>> האלמנט ממוין הבא הוא
שלוש, כך תהיה לנו להגדיר אותו בצד.

46
00:02:16,030 --> 00:02:18,200
אנחנו משמרת על מה שאנחנו
צריך ש, זה זמן

47
00:02:18,200 --> 00:02:21,820
זה לא הכל כמו בעבר
שני מקרים, זה רק חמש.

48
00:02:21,820 --> 00:02:25,440
ואז לתקוע שלושה ב,
בין שתיים וחמש.

49
00:02:25,440 --> 00:02:27,849
>> שש הוא הבאים לא ממוינים
אלמנט למערך.

50
00:02:27,849 --> 00:02:31,140
ולמעשה שש גדול מחמישה, כך
אנחנו אפילו לא צריכים לעשות כל החלפה.

51
00:02:31,140 --> 00:02:35,710
אנחנו רק יכולים טקטיקה שש תקין ל
סוף החלק מסודרים.

52
00:02:35,710 --> 00:02:38,270
>> לבסוף, ארבעה הוא
האלמנט אחרון לא ממוינים.

53
00:02:38,270 --> 00:02:42,060
אז נגדיר אותו בצד, להעביר מעל
האלמנטים שאנחנו צריכים לעבור מעל,

54
00:02:42,060 --> 00:02:43,780
ואז לשים את ארבעה שבו הוא שייך.

55
00:02:43,780 --> 00:02:46,400
ועכשיו נראה, יש לנו סוג
של כל האלמנטים.

56
00:02:46,400 --> 00:02:48,150
שים לב עם הכנסה
סוג, לא היה לנו

57
00:02:48,150 --> 00:02:50,240
ללכת הלוך ושוב על פני המערך.

58
00:02:50,240 --> 00:02:54,720
הלכנו רק על פני המערך
פעם אחת, ואנחנו השתנו דברים

59
00:02:54,720 --> 00:02:59,870
שכבר נתקל, כדי
כדי לפנות מקום לאלמנטים החדשים.

60
00:02:59,870 --> 00:03:02,820
>> אז מה במקרה הגרוע ביותר
תרחיש עם מיון הכנסה?

61
00:03:02,820 --> 00:03:05,090
במקרה הגרוע ביותר,
מערך הוא בסדר הפוך.

62
00:03:05,090 --> 00:03:11,180
אתה צריך לעבור כל אחד ממרכיבי n
עד עמדות n, כולנו זמן

63
00:03:11,180 --> 00:03:12,880
להפוך את ההכנסה.

64
00:03:12,880 --> 00:03:15,720
זה הרבה משתנה.

65
00:03:15,720 --> 00:03:18,014
>> במקרה הטוב ביותר,
מערך ממוין בצורה מושלמת.

66
00:03:18,014 --> 00:03:20,680
וקצת כמו מה שקרה
עם חמש ושש בדוגמא,

67
00:03:20,680 --> 00:03:23,779
שבו אנחנו יכולים פשוט טקטיקה זה ב
מבלי לעשות שום הסטה,

68
00:03:23,779 --> 00:03:24,820
בעצם אנחנו היינו עושים את זה.

69
00:03:24,820 --> 00:03:27,560
>> אם אתה מדמיין ש
מערך היה אחד עד שש,

70
00:03:27,560 --> 00:03:29,900
היינו להתחיל ב
הכרזה אחד ממוין.

71
00:03:29,900 --> 00:03:33,300
שני מגיעים אחרי אחד אז אנחנו פשוט יכולים
אומר, בסדר, גם אחד ושני מסודרים.

72
00:03:33,300 --> 00:03:36,190
שלוש מגיעים לאחר שני כל כך, אישור,
אחד ושתיים ושלושה מסודרים.

73
00:03:36,190 --> 00:03:39,590
>> אנחנו לא עושים שום החלפה, אנחנו
רק נע קו שרירותי זו

74
00:03:39,590 --> 00:03:42,460
בין מסודרים וממוין כמו שאנחנו הולכים.

75
00:03:42,460 --> 00:03:46,646
בצורה יעילה כמו שעשינו בדוגמא,
הפיכת אלמנטים כחולים, ככל שנתקדם.

76
00:03:46,646 --> 00:03:48,270
אז מה המקרה הגרוע ביותר של זמן הריצה, אז?

77
00:03:48,270 --> 00:03:51,854
זכור, אם יש לנו להעביר את כל אחד מ
אלמנטי n אולי עמדות n,

78
00:03:51,854 --> 00:03:54,020
אני מקווה שנותן לך
רעיון שהמקרה הגרוע ביותר

79
00:03:54,020 --> 00:03:57,770
זמן ריצה היא O הגדול של n בריבוע.

80
00:03:57,770 --> 00:04:00,220
>> אם המערך הוא בצורה מושלמת
מסודרים, כל מה שאנחנו צריכים לעשות

81
00:04:00,220 --> 00:04:04,480
הוא מסתכל על כל אלמנט
פעם אחת, ולאחר מכן שנסיים.

82
00:04:04,480 --> 00:04:08,440
אז במקרה הטוב, זה אומגה של n.

83
00:04:08,440 --> 00:04:09,490
>> אני דאג לויד.

84
00:04:09,490 --> 00:04:11,760
זה CS50.

85
00:04:11,760 --> 00:04:13,119