>> [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.