1
00:00:00,000 --> 00:00:02,290
[Powered by Google Translate] [Ordenar Inserció]

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

3
00:00:04,240 --> 00:00:07,290
[Aquesta és CS50.TV]

4
00:00:07,290 --> 00:00:13,060
Anem a fer una ullada a l'ordenació per inserció, un algorisme per a la presa d'una llista de nombres i ordenar-los.

5
00:00:13,060 --> 00:00:18,300
Un algorisme, recordi, és simplement un procediment pas a pas per realitzar una tasca.

6
00:00:18,300 --> 00:00:23,640
La idea bàsica darrere de l'ordenació per inserció, és dividir la llista en dues parts,

7
00:00:23,640 --> 00:00:26,580
una porció ordenats i una porció sense classificar.

8
00:00:26,580 --> 00:00:29,290
>> A cada pas de l'algorisme, un nombre es mou

9
00:00:29,290 --> 00:00:32,439
des de la part no seleccionada a la porció ordenats

10
00:00:32,439 --> 00:00:35,680
fins que finalment tota la llista està ordenada.

11
00:00:35,680 --> 00:00:43,340
Aquesta és la llista de sis números no classificats - 23, 42, 4, 16, 8, i 15.

12
00:00:43,340 --> 00:00:47,680
Atès que aquests nombres no són tot en ordre ascendent, estan sense ordenar.

13
00:00:47,680 --> 00:00:53,890
Com que no hem començat classificació, però, anem a considerar els sis elements de la nostra part sense classificar.

14
00:00:53,890 --> 00:00:59,270
>> Quan comencem la classificació, posarem aquests nombres ordenats a l'esquerra de les mateixes.

15
00:00:59,270 --> 00:01:03,600
Per tant, anem a començar amb 23, el primer element de la llista.

16
00:01:03,600 --> 00:01:06,930
No tenim cap element de la nostra part ordenats, però,

17
00:01:06,930 --> 00:01:12,460
així que considerarem només 23 en ser l'inici i el final de la nostra part ordenada.

18
00:01:12,460 --> 00:01:16,510
Ara, la nostra porció ordenada té un nombre, 23,

19
00:01:16,510 --> 00:01:20,260
i de la nostra part no seleccionada té aquests cinc números.

20
00:01:20,260 --> 00:01:27,320
Ara anem a inserir el següent número de la nostra part sense classificar, de 42 anys, a la part ordenada.

21
00:01:27,320 --> 00:01:35,930
>> Per això, haurem de comparar la 42 a la 23 - l'únic element en la nostra porció ordenats fins ara.

22
00:01:35,930 --> 00:01:41,980
Quaranta-dos és més gran que 23, de manera que simplement pot afegir 42 fins al final

23
00:01:41,980 --> 00:01:45,420
de la part ordenada de la llista. Great!

24
00:01:45,420 --> 00:01:51,850
Ara la nostra part segons consta de dos elements, i la nostra part no seleccionada té quatre elements.

25
00:01:51,850 --> 00:01:57,200
Per tant, passarem ara a la 4, el següent de la part sense classificar.

26
00:01:57,200 --> 00:02:00,230
Així, on ha de ser col · locat en aquesta porció de la ordenats?

27
00:02:00,230 --> 00:02:04,220
>> Recordeu, volem posar aquest nombre en forma ordenada

28
00:02:04,220 --> 00:02:08,680
pel que la nostra porció ordenats roman correctament ordenats en tot moment.

29
00:02:08,680 --> 00:02:14,380
Si col · loquem la 4 a la dreta dels 42, llavors la nostra llista estarà fora d'ordre.

30
00:02:14,380 --> 00:02:18,380
Per tant, continuarem movent de dreta a esquerra en la nostra porció de classificació.

31
00:02:18,380 --> 00:02:23,260
A mesura que avancem, passarem per cada nombre un lloc per fer espai per al nou nombre.

32
00:02:25,440 --> 00:02:31,740
Val, 4 també és inferior a 23, pel que no es pot col · locar aquí tampoc.

33
00:02:31,740 --> 00:02:34,480
Anem a passar el 23 a la dreta un sol lloc.

34
00:02:36,500 --> 00:02:43,120
>> Això vol dir que ens agradaria posar el 4 a la primera ranura a la part ordenada.

35
00:02:43,120 --> 00:02:46,300
Observi com aquest espai a la llista ja estava buida,

36
00:02:46,300 --> 00:02:51,120
perquè hem estat movent elements ordenats a mesura que els hem trobat.

37
00:02:51,120 --> 00:02:52,740
Està bé. Per tant, estem a mig camí.

38
00:02:52,740 --> 00:02:57,990
Continuarem el nostre algorisme mitjançant la inserció de la 16 a la part ordenada.

39
00:02:59,260 --> 00:03:03,820
Setze és menys de 42, així que passarem el 42 a la dreta.

40
00:03:05,700 --> 00:03:10,190
Setze és també menys de 23, així que anem a canviar també aquest element.

41
00:03:11,790 --> 00:03:20,820
>> Ara, 16 és més gran que 4. Per tant, sembla que ens agradaria inserir la 16 entre el 4 i 23 de la.

42
00:03:20,820 --> 00:03:24,620
Mentre es mou a través de la porció de la llista ordenada de dreta a esquerra,

43
00:03:24,620 --> 00:03:29,160
4 és el primer número hem vist que és menor que el nombre

44
00:03:29,160 --> 00:03:31,540
estem tractant d'inserir.

45
00:03:31,540 --> 00:03:35,820
Per tant, ara podem inserir els 16 en aquesta ranura buida,

46
00:03:35,820 --> 00:03:40,520
que, recordem, hem creat per elements en moviment a la part de tipus més

47
00:03:40,520 --> 00:03:43,340
com els hem trobat.

48
00:03:43,340 --> 00:03:47,900
>> Està bé. Ara, tenim quatre elements ordenats i dos elements no ordenats.

49
00:03:47,900 --> 00:03:51,600
Per tant, passarem el 8 a la part ordenada.

50
00:03:51,600 --> 00:03:55,010
Vuit és inferior a 42.

51
00:03:55,010 --> 00:03:56,940
Vuit és menys de 23.

52
00:03:56,940 --> 00:04:00,230
I 8 és menor que 16.

53
00:04:00,230 --> 00:04:03,110
Però 8 és major que 4.

54
00:04:03,110 --> 00:04:07,280
Per tant, ens agradaria introduir el 8 entre el 4 i el 16.

55
00:04:09,070 --> 00:04:13,650
I ara només tenim un element més a l'esquerra per ordenar - el 15.

56
00:04:13,950 --> 00:04:16,589
Quinze és inferior a 42,

57
00:04:16,589 --> 00:04:19,130
Quinze és menys de 23.

58
00:04:19,130 --> 00:04:21,750
I 15 és menor que 16.

59
00:04:21,750 --> 00:04:24,810
Però 15 és més gran que 8.

60
00:04:24,810 --> 00:04:27,440
>> Així doncs, aquí és on volem que la nostra inserció final.

61
00:04:28,770 --> 00:04:30,330
I hem acabat.

62
00:04:30,330 --> 00:04:33,540
No tenim més elements en la porció sense classificar,

63
00:04:33,540 --> 00:04:36,670
i la nostra porció ordenats en l'ordre correcte.

64
00:04:36,670 --> 00:04:40,270
Els nombres estan ordenats de menor a major.

65
00:04:40,270 --> 00:04:44,330
Per tant, donem una ullada a alguns pseudocodi que descriu els passos que acabem de realitzar.

66
00:04:46,760 --> 00:04:51,740
>> A la línia 1, podem veure que necessitarem per iterar sobre cada element de la llista

67
00:04:51,740 --> 00:04:57,060
excepte el primer, ja que el primer element en la part no seleccionada es farà simplement

68
00:04:57,060 --> 00:05:00,220
la primera tasca a la part ordenats.

69
00:05:00,220 --> 00:05:06,320
A les línies 2 i 3, estem mantenint un seguiment de la nostra posició actual a la part sense classificar.

70
00:05:06,320 --> 00:05:10,450
Element representa el nombre que s'està movent en la part de classificats,

71
00:05:10,450 --> 00:05:15,600
i j representa el nostre índex a la part sense classificar.

72
00:05:15,600 --> 00:05:20,980
>> En la línia 4, estem iterant a través de la porció ordenats de dreta a esquerra.

73
00:05:20,980 --> 00:05:26,010
Volem deixar de iterar un cop que l'element a l'esquerra de la seva posició actual

74
00:05:26,010 --> 00:05:30,050
és menor que l'element que estem tractant d'inserir.

75
00:05:30,050 --> 00:05:35,600
A la línia 5, estem canviant cada element que trobem un espai a la dreta.

76
00:05:35,600 --> 00:05:40,950
D'aquesta manera, tindrem un espai lliure per a inserir en tant ens trobem amb el primer element

77
00:05:40,950 --> 00:05:44,080
menor que l'element que s'està movent.

78
00:05:44,080 --> 00:05:50,800
En la línia 6, estem actualitzant el nostre comptador a continuar movent-se a l'esquerra per la part ordenada.

79
00:05:50,800 --> 00:05:56,860
Finalment, en la línia 7, estem inserir l'element dins de la part de la llista ordenada.

80
00:05:56,860 --> 00:06:00,020
>> Sabem que està bé per inserir en la posició j,

81
00:06:00,020 --> 00:06:05,360
perquè ja hem mogut l'element que solia ser-hi un espai a la dreta.

82
00:06:05,360 --> 00:06:09,460
Recordeu, ens estem movent a través de la porció ordenats de dreta a esquerra,

83
00:06:09,460 --> 00:06:13,960
però ens estem movent a través de la part no seleccionada d'esquerra a dreta.

84
00:06:13,960 --> 00:06:19,090
Està bé. Fem una ullada a com de llarga data que es algorisme.

85
00:06:19,090 --> 00:06:25,300
En primer lloc, vaig a fer la pregunta quant de temps es necessita perquè aquest algorisme s'executi en el pitjor dels casos.

86
00:06:25,300 --> 00:06:29,040
Recordem que representem aquesta vegada corrent amb la notació gran O.

87
00:06:32,530 --> 00:06:38,500
Per ordenar la llista, vam haver iterar sobre els elements de la part sense classificar,

88
00:06:38,500 --> 00:06:43,430
i per a cada un d'aquests elements, potencialment a través de tots els elements en la porció ordenats.

89
00:06:43,430 --> 00:06:47,950
Intuïtivament, això sona com una operació O (n ^ 2).

90
00:06:47,950 --> 00:06:51,840
>> Quant al nostre pseudocodi, tenim un bucle niat dins d'un altre bucle,

91
00:06:51,840 --> 00:06:55,290
que, de fet, sona com una operació O (n ^ 2).

92
00:06:55,290 --> 00:07:01,590
No obstant això, la part ordenada de llista no contenia tota la llista fins al final.

93
00:07:01,590 --> 00:07:06,920
Tot i això, podria inserir un nou element en el començament mateix de la porció ordenats

94
00:07:06,920 --> 00:07:09,320
en cada iteració de l'algorisme,

95
00:07:09,320 --> 00:07:14,500
el que significa que hauríem de mirar cada element actualment a la part ordenada.

96
00:07:14,500 --> 00:07:20,090
Per tant, això vol dir que potencialment podria fer una comparació per al segon element,

97
00:07:20,090 --> 00:07:24,660
dues comparacions per al tercer element, i així successivament.

98
00:07:24,660 --> 00:07:32,480
Així, el nombre total de passos és la suma dels enters d'1 a la longitud de la llista menys 1.

99
00:07:32,480 --> 00:07:35,240
Podem representar això amb una suma.

100
00:07:41,170 --> 00:07:47,270
>> No entrarem en sumes aquí, però resulta que aquesta suma és igual a

101
00:07:47,270 --> 00:07:57,900
n (n - 1) sobre 2, que és equivalent n ^ 2/2 - n / 2.

102
00:07:57,900 --> 00:08:00,800
Quan es parla de temps d'execució asimptòtic,

103
00:08:00,800 --> 00:08:05,170
aquest n ^ 2 termini va a dominar aquest terme n.

104
00:08:05,170 --> 00:08:11,430
Per tant, l'ordenació per inserció és Big O (n ^ 2).

105
00:08:11,430 --> 00:08:16,150
Què passa si ens quedem ordenació per inserció en una llista ja ordenada.

106
00:08:16,150 --> 00:08:20,960
En aquest cas, simplement s'havia acumulació de la porció ordenats d'esquerra a dreta.

107
00:08:20,960 --> 00:08:25,050
Així que l'únic que necessita de l'ordre de n passos.

108
00:08:25,050 --> 00:08:29,740
>> Això significa que l'ordenació per inserció té un rendiment millor dels casos de n,

109
00:08:29,740 --> 00:08:34,130
que representem amb Ω (n).

110
00:08:34,130 --> 00:08:36,190
I això és tot per tipus d'inserció,

111
00:08:36,190 --> 00:08:40,429
només un dels molts algoritmes que es poden utilitzar per ordenar una llista.

112
00:08:40,429 --> 00:08:43,210
El meu nom és Tommy, i això és CS50.

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

114
00:08:46,110 --> 00:08:49,230
Oh, no pots deixar que una vegada que s'iniciï.

115
00:09:01,620 --> 00:09:04,760
Oh, ho vam fer - Boom! >>