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
Како го прави ова алгоритам
работат во pseudocode?

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
И ајде да ги следат
чекори на нашата pseudocode.

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
траење е Биг О од 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