1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [După Insertion]

2
00:00:02,290 --> 00:00:04,240
[Tommy MacWilliam] [Universitatea Harvard]

3
00:00:04,240 --> 00:00:07,290
[Acest lucru este CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Să aruncăm o privire la fel de inserare, un algoritm pentru a lua o listă de numere și sortarea lor.

5
00:00:13,060 --> 00:00:18,300
Un algoritm, amintiți-vă, este pur și simplu o procedură pas-cu-pas pentru realizarea unei sarcini.

6
00:00:18,300 --> 00:00:23,640
Ideea de bază din spatele fel de inserare, este de a împărți lista noastră de în două tranșe,

7
00:00:23,640 --> 00:00:26,580
o parte sortati si o parte nesortate.

8
00:00:26,580 --> 00:00:29,290
>> La fiecare pas al algoritmului, un număr este mutat

9
00:00:29,290 --> 00:00:32,439
din partea nesortate la porțiunea sortate

10
00:00:32,439 --> 00:00:35,680
până când în cele din urmă intreaga lista este sortată.

11
00:00:35,680 --> 00:00:43,340
Iată lista cu șase numere nesortate - 23, 42, 4, 16, 8, și 15.

12
00:00:43,340 --> 00:00:47,680
Întrucât aceste numere nu sunt în ordine crescătoare, acestea sunt sortate.

13
00:00:47,680 --> 00:00:53,890
Din moment ce nu am început încă de sortare, vom lua în considerare toate cele șase elemente de partea noastră nesortate.

14
00:00:53,890 --> 00:00:59,270
>> Odată ce vom începe sortarea, vom pune aceste numere sortate la stânga dintre acestea.

15
00:00:59,270 --> 00:01:03,600
Deci, să începem cu 23, primul element din lista noastră.

16
00:01:03,600 --> 00:01:06,930
Noi nu avem nici un element din partea noastră sortate încă,

17
00:01:06,930 --> 00:01:12,460
așa că hai să ia în considerare pur și simplu să fie 23 începutul și sfârșitul partea noastră sortate.

18
00:01:12,460 --> 00:01:16,510
Acum, partea noastră sortate are un număr, 23,

19
00:01:16,510 --> 00:01:20,260
și partea noastră nesortate are aceste cinci numere.

20
00:01:20,260 --> 00:01:27,320
Să se introduce acum urmatorul numar din partea noastră nesortate, 42, în partea sortate.

21
00:01:27,320 --> 00:01:35,930
>> Pentru a face acest lucru, vom avea nevoie pentru a compara 42 până la 23 - singurul element din partea noastră sortate până în prezent.

22
00:01:35,930 --> 00:01:41,980
Patruzeci și doi este mai mare decât 23, astfel încât să putem adăuga pur și simplu la 42 la sfârșitul anului

23
00:01:41,980 --> 00:01:45,420
de porțiunea de sortat lista. Minunat!

24
00:01:45,420 --> 00:01:51,850
Acum partea noastră are două elemente sortate, iar partea noastră nesortate are patru elemente.

25
00:01:51,850 --> 00:01:57,200
Deci, să trecem acum la 4, urmatorul element din partea nesortata.

26
00:01:57,200 --> 00:02:00,230
Deci, în cazul în care ar trebui să fie plasate în această porțiune sortate?

27
00:02:00,230 --> 00:02:04,220
>> Amintiți-vă, vrem să pună acest număr, în ordine sortate

28
00:02:04,220 --> 00:02:08,680
astfel încât partea noastră rămâne sortate în mod corect sortate în orice moment.

29
00:02:08,680 --> 00:02:14,380
Dacă punem 4 la dreapta 42, atunci lista noastră va fi în ordine.

30
00:02:14,380 --> 00:02:18,380
Deci, hai să continue să acționeze de la dreapta la stânga, în partea de sortare nostru.

31
00:02:18,380 --> 00:02:23,260
Pe masura ce inaintam, să transfere fiecare număr în jos un loc pentru a face loc pentru noul număr.

32
00:02:25,440 --> 00:02:31,740
Bine, 4 este, de asemenea, mai puțin de 23, deci nu-l putem plasa nici aici.

33
00:02:31,740 --> 00:02:34,480
Să trecem 23 dreptul de-un singur loc.

34
00:02:36,500 --> 00:02:43,120
>> Asta înseamnă că am dori să plasați 4 în primul slot din partea sortate.

35
00:02:43,120 --> 00:02:46,300
Observați cum acest spațiu în lista era deja gol,

36
00:02:46,300 --> 00:02:51,120
pentru că am fost în mișcare elemente sortate după cum le-am întâlnit.

37
00:02:51,120 --> 00:02:52,740
Bine. Deci, suntem la jumătatea drumului.

38
00:02:52,740 --> 00:02:57,990
Să continuăm algoritmul nostru prin inserarea în 16 porțiunea sortate.

39
00:02:59,260 --> 00:03:03,820
Șaisprezece este mai mică de 42, asa ca hai sa transfere 42 la dreapta.

40
00:03:05,700 --> 00:03:10,190
Șaisprezece este, de asemenea, mai puțin de 23, asa ca hai sa schimba, de asemenea, că acest element.

41
00:03:11,790 --> 00:03:20,820
>> Acum, 16 este mai mare de 4. Deci, se pare ca ne-am dori pentru a insera 16 dintre 4 și 23.

42
00:03:20,820 --> 00:03:24,620
În timp ce se deplasează prin porțiunea de sortat lista de la dreapta la stânga,

43
00:03:24,620 --> 00:03:29,160
4 este primul număr am văzut că este mai mic decât numărul

44
00:03:29,160 --> 00:03:31,540
încercăm să inserați.

45
00:03:31,540 --> 00:03:35,820
Deci, acum putem introduce 16 in acest slot gol,

46
00:03:35,820 --> 00:03:40,520
care, amintiți-vă, am creat cu elemente în mișcare în partea de sortare de peste

47
00:03:40,520 --> 00:03:43,340
cum le-am întâlnit.

48
00:03:43,340 --> 00:03:47,900
>> Bine. Acum, avem patru elemente sunt sortate și două elemente nesortate.

49
00:03:47,900 --> 00:03:51,600
Deci, să trecem în partea 8 sortate.

50
00:03:51,600 --> 00:03:55,010
Opt este mai mică de 42.

51
00:03:55,010 --> 00:03:56,940
Opt este mai mică de 23.

52
00:03:56,940 --> 00:04:00,230
Și 8 este mai mică de 16.

53
00:04:00,230 --> 00:04:03,110
Dar 8 este mai mare de 4.

54
00:04:03,110 --> 00:04:07,280
Deci, am dori pentru a insera 8 dintre 4 și 16.

55
00:04:09,070 --> 00:04:13,650
Și acum avem doar un element mai rămas pentru a sorta - 15.

56
00:04:13,950 --> 00:04:16,589
Cincisprezece este mai mică de 42,

57
00:04:16,589 --> 00:04:19,130
Cincisprezece este mai mică de 23.

58
00:04:19,130 --> 00:04:21,750
Și 15 este mai mică de 16.

59
00:04:21,750 --> 00:04:24,810
Dar 15 este mai mare de 8.

60
00:04:24,810 --> 00:04:27,440
>> Deci, aici este locul unde dorim să facem inserarea nostru final.

61
00:04:28,770 --> 00:04:30,330
Și am terminat.

62
00:04:30,330 --> 00:04:33,540
Noi nu avem mai multe elemente în partea nesortate,

63
00:04:33,540 --> 00:04:36,670
și partea noastră este sortate în ordinea corectă.

64
00:04:36,670 --> 00:04:40,270
Numerele sunt ordonate de la cel mai mic la cel mai mare.

65
00:04:40,270 --> 00:04:44,330
Deci, haideți să aruncăm o privire la unele pseudocod, care descrie pașii ne-am efectuat.

66
00:04:46,760 --> 00:04:51,740
>> Pe linia 1, putem vedea că vom avea nevoie pentru a itera peste fiecare element din listă

67
00:04:51,740 --> 00:04:57,060
cu excepția primei, deoarece primul element din partea nesortata va deveni pur și simplu

68
00:04:57,060 --> 00:05:00,220
primul element în porțiunea sortate.

69
00:05:00,220 --> 00:05:06,320
Pe liniile 2 și 3, suntem urmărirea locul nostru curent în porțiunea nesortate.

70
00:05:06,320 --> 00:05:10,450
Element reprezintă numărul suntem în prezent se deplasează în partea sortate,

71
00:05:10,450 --> 00:05:15,600
și j reprezintă indexul nostru în porțiunea nesortate.

72
00:05:15,600 --> 00:05:20,980
>> Pe linia 4, suntem iterarea prin porțiunea sortate de la dreapta la stânga.

73
00:05:20,980 --> 00:05:26,010
Ne dorim să oprim iterarea o dată elementul la stânga poziției noastre actuale

74
00:05:26,010 --> 00:05:30,050
este mai mică decât elementul noi încercăm să inserați.

75
00:05:30,050 --> 00:05:35,600
Pe linia 5, suntem schimbarea fiecarui element ne întâlnim cu un spațiu la dreapta.

76
00:05:35,600 --> 00:05:40,950
În acest fel, vom avea un spațiu liber pentru a insera în când vom găsi primul element

77
00:05:40,950 --> 00:05:44,080
mai puțin elementul ne mișcăm.

78
00:05:44,080 --> 00:05:50,800
Pe linia 6, suntem actualizarea contra noastră de a continua să se deplaseze lăsat prin porțiunea sortate.

79
00:05:50,800 --> 00:05:56,860
În cele din urmă, pe linia 7, vom introduce elementul în partea de sortat lista.

80
00:05:56,860 --> 00:06:00,020
>> Știm că e în regulă să inserați în poziția j,

81
00:06:00,020 --> 00:06:05,360
pentru că ne-am mutat deja elementul care a folosit pentru a fi acolo un spațiu la dreapta.

82
00:06:05,360 --> 00:06:09,460
Amintiți-vă, ne mișcăm prin porțiunea sortate de la dreapta la stânga,

83
00:06:09,460 --> 00:06:13,960
dar ne mișcăm prin porțiunea nesortate de la stânga la dreapta.

84
00:06:13,960 --> 00:06:19,090
Bine. Să aruncăm acum o privire la modul de mult de rulare, care a avut algoritm.

85
00:06:19,090 --> 00:06:25,300
Vom întreba mai întâi întrebarea cât timp durează pentru acest algoritm pentru a rula în cel mai rău caz.

86
00:06:25,300 --> 00:06:29,040
Reamintească faptul că ne reprezintă de această dată de rulare cu notația Big O.

87
00:06:32,530 --> 00:06:38,500
În scopul de a sorta lista noastră, am avut pentru a itera peste elementele din partea nesortate,

88
00:06:38,500 --> 00:06:43,430
și pentru fiecare dintre aceste elemente, cu potențial peste toate elementele din partea sortate.

89
00:06:43,430 --> 00:06:47,950
Intuitiv, acest lucru sună ca un O (n ^ 2) operațiunea.

90
00:06:47,950 --> 00:06:51,840
>> Privind la pseudocod nostru, avem o buclă imbricată într-o altă buclă,

91
00:06:51,840 --> 00:06:55,290
care, într-adevăr, sună ca un O (n ^ 2) operațiunea.

92
00:06:55,290 --> 00:07:01,590
Cu toate acestea, partea sortate de listă nu conține întreaga listă până la sfârșitul foarte.

93
00:07:01,590 --> 00:07:06,920
Cu toate acestea, am putea introduce un element nou potential, la începutul porțiunii sortate

94
00:07:06,920 --> 00:07:09,320
pe fiecare iterație a algoritmului,

95
00:07:09,320 --> 00:07:14,500
ceea ce înseamnă că vom avea să se uite la fiecare element prezent în porțiunea sortate.

96
00:07:14,500 --> 00:07:20,090
Deci, asta înseamnă că am putea face o comparatie potential pentru al doilea element,

97
00:07:20,090 --> 00:07:24,660
două comparații pentru al treilea element, și așa mai departe.

98
00:07:24,660 --> 00:07:32,480
Deci, numărul total de pași este suma intregi de la 1 la lungimea listei minus 1.

99
00:07:32,480 --> 00:07:35,240
Ne putem reprezenta acest lucru cu o însumare.

100
00:07:41,170 --> 00:07:47,270
>> Nu vom intra în somații aici, dar se pare că acest lucru este egal cu însumării

101
00:07:47,270 --> 00:07:57,900
n (n - 1) pe 2, ceea ce este echivalent cu n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Atunci când vorbim despre timpul rulării asimptotică,

103
00:08:00,800 --> 00:08:05,170
acest termen n ^ 2 este de gând să domine acest termen nr.

104
00:08:05,170 --> 00:08:11,430
Deci, un fel de inserare este Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Ce se întâmplă dacă am alergat un fel inserarea pe o listă deja sortate.

106
00:08:16,150 --> 00:08:20,960
În acest caz, vom construi pur și simplu partea sortate de la stânga la dreapta.

107
00:08:20,960 --> 00:08:25,050
Deci, vom avea nevoie de doar pe ordinea de pași n.

108
00:08:25,050 --> 00:08:29,740
>> Asta înseamnă că un fel de inserare are o performanță mai bună-n caz de,

109
00:08:29,740 --> 00:08:34,130
pe care le reprezintă cu Ω (n).

110
00:08:34,130 --> 00:08:36,190
Și asta e tot pentru sortare inserarea,

111
00:08:36,190 --> 00:08:40,429
doar unul din algoritmii de mai multe le putem folosi pentru a sorta o listă.

112
00:08:40,429 --> 00:08:43,210
Numele meu este Tommy, iar acest lucru este CS50.

113
00:08:43,210 --> 00:08:44,880
[CS50.TV]

114
00:08:46,110 --> 00:08:49,230
Oh, tu chiar nu se poate opri că odată ce începe.

115
00:09:01,620 --> 00:09:04,760
Oh, am făcut asta - Boom >>!