[REPRODUCCIÓ DE MÚSICA] 

DOUG LLOYD: Així ordenació per inserció és un altre algoritme que pot utilitzar per ordenar una matriu. La idea darrere d'aquest algorisme és la construcció de la seva matriu ordenada en el seu lloc, els elements de desplaçament de el camí a mesura que avança, per fer espai. Això és lleugerament diferent des de la selecció del tipus o de la bombolla Ordena, per exemple, on estem ajustant els llocs, on estem fent swaps. 

En aquest cas el que som en realitat fent és elements lliscants una altra vegada, fora del camí. Com funciona aquest algoritme treballar en pseudocodi? Bé anem a dir simplement que la forma arbitrària primer element de la matriu s'ordena. Estem construint al seu lloc. 

Anirem un element a la vegada i construir-lo, de manera que la primera cosa que veiem és una matriu d'un element. I, per definició, una element de la matriu s'ordena. 

Llavors repetirem aquest procés until-- repetirem el següent procés fins que tots els elements són ordenats. Mira el següent element no seleccionats i inserir-lo en la part ordenada, desplaçant el nombre requerit d'elements fora del camí. Esperem que aquesta visualització l'ajudarà a veure exactament el que està passant amb l'ordenació per inserció. 

Així que de nou, aquí està la nostra tota varietat sense classificar, tots els elements indicats en vermell. I continuarem la passos de la nostra pseudocodi. La primera cosa que fem, se'ns crida a la primer element de la matriu, ordenats. Així que només direm 5, ara ets ordenats. 

Llavors ens fixem en la següent element sense classificar de la matriu i volem inserir aquest en la porció ordenats, per elements de desplaçament sobre. Així que dos és la següent sense classificar element de la matriu. És evident que pertany abans de la cinc, així que el que farem és una espècie de sostenir de dos de costat per un segon, canviar de cinc més, i després inseriu de dos abans de les cinc, on ha d'anar. I ara podem dir que dos s'ordena. 

Així com vostè pot veure, només hem fins ara mirat dos elements de la matriu. No hem mirat el descansem en absolut, sinó que hem van aconseguir aquests dos elements ordenats per camí del mecanisme de canvi. 

Així que repetim el procés de nou. Mira la següent sense classificar element, que és un. Anem a celebrar això de banda per un segon, canviar tot el més, i posar un on ha d'anar. 

Un cop més, tot i així, només he va mirar a un, dos-cinc. No sabem què més està per venir, però hem van solucionar aquests tres elements. 

Element sense classificar següent és tres, pel que establirem a un costat. Ens desplacem sobre el que necessitarà que, aquest cop no ho és tot com en l'anterior ambdós casos, és només el cinc. I llavors ens mantindrem tres a, entre els dos i els cinc. 

Sis és el següent sense classificar element a la matriu. I de fet 6 és superior a cinc, per la qual que ni tan sols ens cal fer cap intercanvi. Només podem virar i sis a la dreta en l'extrem de la porció ordenats. 

Finalment, quatre és el últim element sense classificar. Així que establirem una banda, canviem més els elements que han de canviar al llarg, i després posar les quatre que li correspon. I ara mira, tenim una espècie de tots els elements. Avís de la inserció espècie, no teníem per anar i venir a través de la matriu. Nosaltres només vam anar a través de la matriu una sola vegada, i ens va canviar les coses que ja havíem trobat, per tal per donar cabuda als nous elements. 

Quin és el pitjor dels casos escenari amb l'ordenació per inserció? En el pitjor dels casos, la array és en ordre invers. Vostè ha de canviar cadascun dels n elements fins an posicions, tots tenim una sola vegada fer una inserció. Això és un munt de canviar. 

En el millor dels casos, la matriu està perfectament ordenades. I alguna cosa així com el que va passar amb cinc i sis a l'exemple, en el qual només podíem virar en sense haver de fer cap canvi, que essencialment faríem això. 

Si vostè s'imagina que el nostre matriu va ser l'u al sis, ens agradaria començar per declarant un sol està ordenada. Dos ve després que un pel que pot simplement diuen, OK, bo 1:02 són ordenats. Tres ve després de dos, així, està bé, un-dos i tres són ordenats. 

No estem fent cap swaps, estem només moure aquesta línia arbitrària entre classificats i no classificats a mesura que avancem. Com efectivament com ho vam fer en l'exemple, convertir elements blau, a mesura que avancem. Llavors, què és el pitjor d'execució cas, llavors? Recordeu, si hem de canviar cadascun els n elements possiblement n posicions, espero que et dóna una idea que el pitjor dels casos temps d'execució és O gran de n al quadrat. 

Si la matriu és perfectament ordenat, tot el que hem de fer és mirar a cada element una vegada, i després hem acabat. Així que en el millor dels casos, és l'omega de n. 

Sóc Doug Lloyd. Això és CS50.