1
00:00:00,000 --> 00:00:02,826
>> [REPRODUCCIÓ DE MÚSICA]

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

3
00:00:05,660 --> 00:00:09,370
>> DOUG LLOYD: Així ordenació per inserció és un altre
algoritme que pot utilitzar per ordenar una matriu.

4
00:00:09,370 --> 00:00:12,350
La idea darrere d'aquest algorisme
és la construcció de la seva matriu ordenada

5
00:00:12,350 --> 00:00:19,670
en el seu lloc, els elements de desplaçament de
el camí a mesura que avança, per fer espai.

6
00:00:19,670 --> 00:00:22,240
Això és lleugerament diferent
des de la selecció del tipus o de la bombolla

7
00:00:22,240 --> 00:00:25,460
Ordena, per exemple, on
estem ajustant els llocs,

8
00:00:25,460 --> 00:00:26,910
on estem fent swaps.

9
00:00:26,910 --> 00:00:29,760
>> En aquest cas el que som en realitat
fent és elements lliscants

10
00:00:29,760 --> 00:00:31,390
una altra vegada, fora del camí.

11
00:00:31,390 --> 00:00:34,030
Com funciona aquest algoritme
treballar en pseudocodi?

12
00:00:34,030 --> 00:00:37,646
Bé anem a dir simplement que la forma arbitrària
primer element de la matriu s'ordena.

13
00:00:37,646 --> 00:00:38,770
Estem construint al seu lloc.

14
00:00:38,770 --> 00:00:42,660
>> Anirem un element a la vegada i
construir-lo, de manera que la primera cosa que veiem

15
00:00:42,660 --> 00:00:43,890
és una matriu d'un element.

16
00:00:43,890 --> 00:00:47,720
I, per definició, una
element de la matriu s'ordena.

17
00:00:47,720 --> 00:00:50,850
>> Llavors repetirem aquest procés until--
repetirem el següent procés

18
00:00:50,850 --> 00:00:52,900
fins que tots els elements són ordenats.

19
00:00:52,900 --> 00:00:57,770
Mira el següent element no seleccionats i
inserir-lo en la part ordenada,

20
00:00:57,770 --> 00:01:01,209
desplaçant el nombre requerit
d'elements fora del camí.

21
00:01:01,209 --> 00:01:03,750
Esperem que aquesta visualització
l'ajudarà a veure exactament el que està

22
00:01:03,750 --> 00:01:05,980
passant amb l'ordenació per inserció.

23
00:01:05,980 --> 00:01:08,010
>> Així que de nou, aquí està la nostra
tota varietat sense classificar,

24
00:01:08,010 --> 00:01:10,970
tots els elements indicats en vermell.

25
00:01:10,970 --> 00:01:13,320
I continuarem la
passos de la nostra pseudocodi.

26
00:01:13,320 --> 00:01:16,970
La primera cosa que fem, se'ns crida a la
primer element de la matriu, ordenats.

27
00:01:16,970 --> 00:01:20,920
Així que només direm
5, ara ets ordenats.

28
00:01:20,920 --> 00:01:24,570
>> Llavors ens fixem en la següent
element sense classificar de la matriu

29
00:01:24,570 --> 00:01:27,610
i volem inserir aquest
en la porció ordenats,

30
00:01:27,610 --> 00:01:29,750
per elements de desplaçament sobre.

31
00:01:29,750 --> 00:01:33,470
Així que dos és la següent sense classificar
element de la matriu.

32
00:01:33,470 --> 00:01:36,250
És evident que pertany abans de la
cinc, així que el que farem

33
00:01:36,250 --> 00:01:41,580
és una espècie de sostenir de dos de costat per un segon,
canviar de cinc més, i després inseriu de dos

34
00:01:41,580 --> 00:01:43,210
abans de les cinc, on ha d'anar.

35
00:01:43,210 --> 00:01:45,280
I ara podem dir que dos s'ordena.

36
00:01:45,280 --> 00:01:48,400
>> Així com vostè pot veure, només hem fins ara
mirat dos elements de la matriu.

37
00:01:48,400 --> 00:01:50,600
No hem mirat el
descansem en absolut, sinó que hem

38
00:01:50,600 --> 00:01:54,582
van aconseguir aquests dos elements ordenats per
camí del mecanisme de canvi.

39
00:01:54,582 --> 00:01:56,410
>> Així que repetim el procés de nou.

40
00:01:56,410 --> 00:01:58,850
Mira la següent sense classificar
element, que és un.

41
00:01:58,850 --> 00:02:04,010
Anem a celebrar això de banda per un segon,
canviar tot el més, i posar un

42
00:02:04,010 --> 00:02:05,570
on ha d'anar.

43
00:02:05,570 --> 00:02:08,110
>> Un cop més, tot i així, només he
va mirar a un, dos-cinc.

44
00:02:08,110 --> 00:02:12,480
No sabem què més està per venir,
però hem van solucionar aquests tres elements.

45
00:02:12,480 --> 00:02:16,030
>> Element sense classificar següent és
tres, pel que establirem a un costat.

46
00:02:16,030 --> 00:02:18,200
Ens desplacem sobre el que
necessitarà que, aquest cop

47
00:02:18,200 --> 00:02:21,820
no ho és tot com en l'anterior
ambdós casos, és només el cinc.

48
00:02:21,820 --> 00:02:25,440
I llavors ens mantindrem tres a,
entre els dos i els cinc.

49
00:02:25,440 --> 00:02:27,849
>> Sis és el següent sense classificar
element a la matriu.

50
00:02:27,849 --> 00:02:31,140
I de fet 6 és superior a cinc, per la qual
que ni tan sols ens cal fer cap intercanvi.

51
00:02:31,140 --> 00:02:35,710
Només podem virar i sis a la dreta en
l'extrem de la porció ordenats.

52
00:02:35,710 --> 00:02:38,270
>> Finalment, quatre és el
últim element sense classificar.

53
00:02:38,270 --> 00:02:42,060
Així que establirem una banda, canviem més
els elements que han de canviar al llarg,

54
00:02:42,060 --> 00:02:43,780
i després posar les quatre que li correspon.

55
00:02:43,780 --> 00:02:46,400
I ara mira, tenim una espècie
de tots els elements.

56
00:02:46,400 --> 00:02:48,150
Avís de la inserció
espècie, no teníem

57
00:02:48,150 --> 00:02:50,240
per anar i venir a través de la matriu.

58
00:02:50,240 --> 00:02:54,720
Nosaltres només vam anar a través de la matriu
una sola vegada, i ens va canviar les coses

59
00:02:54,720 --> 00:02:59,870
que ja havíem trobat, per tal
per donar cabuda als nous elements.

60
00:02:59,870 --> 00:03:02,820
>> Quin és el pitjor dels casos
escenari amb l'ordenació per inserció?

61
00:03:02,820 --> 00:03:05,090
En el pitjor dels casos, la
array és en ordre invers.

62
00:03:05,090 --> 00:03:11,180
Vostè ha de canviar cadascun dels n elements
fins an posicions, tots tenim una sola vegada

63
00:03:11,180 --> 00:03:12,880
fer una inserció.

64
00:03:12,880 --> 00:03:15,720
Això és un munt de canviar.

65
00:03:15,720 --> 00:03:18,014
>> En el millor dels casos, la
matriu està perfectament ordenades.

66
00:03:18,014 --> 00:03:20,680
I alguna cosa així com el que va passar
amb cinc i sis a l'exemple,

67
00:03:20,680 --> 00:03:23,779
en el qual només podíem virar en
sense haver de fer cap canvi,

68
00:03:23,779 --> 00:03:24,820
que essencialment faríem això.

69
00:03:24,820 --> 00:03:27,560
>> Si vostè s'imagina que el nostre
matriu va ser l'u al sis,

70
00:03:27,560 --> 00:03:29,900
ens agradaria començar per
declarant un sol està ordenada.

71
00:03:29,900 --> 00:03:33,300
Dos ve després que un pel que pot simplement
diuen, OK, bo 1:02 són ordenats.

72
00:03:33,300 --> 00:03:36,190
Tres ve després de dos, així, està bé,
un-dos i tres són ordenats.

73
00:03:36,190 --> 00:03:39,590
>> No estem fent cap swaps, estem
només moure aquesta línia arbitrària

74
00:03:39,590 --> 00:03:42,460
entre classificats i no classificats a mesura que avancem.

75
00:03:42,460 --> 00:03:46,646
Com efectivament com ho vam fer en l'exemple,
convertir elements blau, a mesura que avancem.

76
00:03:46,646 --> 00:03:48,270
Llavors, què és el pitjor d'execució cas, llavors?

77
00:03:48,270 --> 00:03:51,854
Recordeu, si hem de canviar cadascun
els n elements possiblement n posicions,

78
00:03:51,854 --> 00:03:54,020
espero que et dóna
una idea que el pitjor dels casos

79
00:03:54,020 --> 00:03:57,770
temps d'execució és O gran de n al quadrat.

80
00:03:57,770 --> 00:04:00,220
>> Si la matriu és perfectament
ordenat, tot el que hem de fer

81
00:04:00,220 --> 00:04:04,480
és mirar a cada element
una vegada, i després hem acabat.

82
00:04:04,480 --> 00:04:08,440
Així que en el millor dels casos, és l'omega de n.

83
00:04:08,440 --> 00:04:09,490
>> Sóc Doug Lloyd.

84
00:04:09,490 --> 00:04:11,760
Això és CS50.

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