[Powered by Google Translate] [Ordenar Inserció]
[Tommy MacWilliam] [Harvard University]
[Aquesta és CS50.TV]
Anem a fer una ullada a l'ordenació per inserció, un algorisme per a la presa d'una llista de nombres i ordenar-los.
Un algorisme, recordi, és simplement un procediment pas a pas per realitzar una tasca.
La idea bàsica darrere de l'ordenació per inserció, és dividir la llista en dues parts,
una porció ordenats i una porció sense classificar.
>> A cada pas de l'algorisme, un nombre es mou
des de la part no seleccionada a la porció ordenats
fins que finalment tota la llista està ordenada.
Aquesta és la llista de sis números no classificats - 23, 42, 4, 16, 8, i 15.
Atès que aquests nombres no són tot en ordre ascendent, estan sense ordenar.
Com que no hem començat classificació, però, anem a considerar els sis elements de la nostra part sense classificar.
>> Quan comencem la classificació, posarem aquests nombres ordenats a l'esquerra de les mateixes.
Per tant, anem a començar amb 23, el primer element de la llista.
No tenim cap element de la nostra part ordenats, però,
així que considerarem només 23 en ser l'inici i el final de la nostra part ordenada.
Ara, la nostra porció ordenada té un nombre, 23,
i de la nostra part no seleccionada té aquests cinc números.
Ara anem a inserir el següent número de la nostra part sense classificar, de 42 anys, a la part ordenada.
>> Per això, haurem de comparar la 42 a la 23 - l'únic element en la nostra porció ordenats fins ara.
Quaranta-dos és més gran que 23, de manera que simplement pot afegir 42 fins al final
de la part ordenada de la llista. Great!
Ara la nostra part segons consta de dos elements, i la nostra part no seleccionada té quatre elements.
Per tant, passarem ara a la 4, el següent de la part sense classificar.
Així, on ha de ser col · locat en aquesta porció de la ordenats?
>> Recordeu, volem posar aquest nombre en forma ordenada
pel que la nostra porció ordenats roman correctament ordenats en tot moment.
Si col · loquem la 4 a la dreta dels 42, llavors la nostra llista estarà fora d'ordre.
Per tant, continuarem movent de dreta a esquerra en la nostra porció de classificació.
A mesura que avancem, passarem per cada nombre un lloc per fer espai per al nou nombre.
Val, 4 també és inferior a 23, pel que no es pot col · locar aquí tampoc.
Anem a passar el 23 a la dreta un sol lloc.
>> Això vol dir que ens agradaria posar el 4 a la primera ranura a la part ordenada.
Observi com aquest espai a la llista ja estava buida,
perquè hem estat movent elements ordenats a mesura que els hem trobat.
Està bé. Per tant, estem a mig camí.
Continuarem el nostre algorisme mitjançant la inserció de la 16 a la part ordenada.
Setze és menys de 42, així que passarem el 42 a la dreta.
Setze és també menys de 23, així que anem a canviar també aquest element.
>> Ara, 16 és més gran que 4. Per tant, sembla que ens agradaria inserir la 16 entre el 4 i 23 de la.
Mentre es mou a través de la porció de la llista ordenada de dreta a esquerra,
4 és el primer número hem vist que és menor que el nombre
estem tractant d'inserir.
Per tant, ara podem inserir els 16 en aquesta ranura buida,
que, recordem, hem creat per elements en moviment a la part de tipus més
com els hem trobat.
>> Està bé. Ara, tenim quatre elements ordenats i dos elements no ordenats.
Per tant, passarem el 8 a la part ordenada.
Vuit és inferior a 42.
Vuit és menys de 23.
I 8 és menor que 16.
Però 8 és major que 4.
Per tant, ens agradaria introduir el 8 entre el 4 i el 16.
I ara només tenim un element més a l'esquerra per ordenar - el 15.
Quinze és inferior a 42,
Quinze és menys de 23.
I 15 és menor que 16.
Però 15 és més gran que 8.
>> Així doncs, aquí és on volem que la nostra inserció final.
I hem acabat.
No tenim més elements en la porció sense classificar,
i la nostra porció ordenats en l'ordre correcte.
Els nombres estan ordenats de menor a major.
Per tant, donem una ullada a alguns pseudocodi que descriu els passos que acabem de realitzar.
>> A la línia 1, podem veure que necessitarem per iterar sobre cada element de la llista
excepte el primer, ja que el primer element en la part no seleccionada es farà simplement
la primera tasca a la part ordenats.
A les línies 2 i 3, estem mantenint un seguiment de la nostra posició actual a la part sense classificar.
Element representa el nombre que s'està movent en la part de classificats,
i j representa el nostre índex a la part sense classificar.
>> En la línia 4, estem iterant a través de la porció ordenats de dreta a esquerra.
Volem deixar de iterar un cop que l'element a l'esquerra de la seva posició actual
és menor que l'element que estem tractant d'inserir.
A la línia 5, estem canviant cada element que trobem un espai a la dreta.
D'aquesta manera, tindrem un espai lliure per a inserir en tant ens trobem amb el primer element
menor que l'element que s'està movent.
En la línia 6, estem actualitzant el nostre comptador a continuar movent-se a l'esquerra per la part ordenada.
Finalment, en la línia 7, estem inserir l'element dins de la part de la llista ordenada.
>> Sabem que està bé per inserir en la posició j,
perquè ja hem mogut l'element que solia ser-hi un espai a la dreta.
Recordeu, ens estem movent a través de la porció ordenats de dreta a esquerra,
però ens estem movent a través de la part no seleccionada d'esquerra a dreta.
Està bé. Fem una ullada a com de llarga data que es algorisme.
En primer lloc, vaig a fer la pregunta quant de temps es necessita perquè aquest algorisme s'executi en el pitjor dels casos.
Recordem que representem aquesta vegada corrent amb la notació gran O.
Per ordenar la llista, vam haver iterar sobre els elements de la part sense classificar,
i per a cada un d'aquests elements, potencialment a través de tots els elements en la porció ordenats.
Intuïtivament, això sona com una operació O (n ^ 2).
>> Quant al nostre pseudocodi, tenim un bucle niat dins d'un altre bucle,
que, de fet, sona com una operació O (n ^ 2).
No obstant això, la part ordenada de llista no contenia tota la llista fins al final.
Tot i això, podria inserir un nou element en el començament mateix de la porció ordenats
en cada iteració de l'algorisme,
el que significa que hauríem de mirar cada element actualment a la part ordenada.
Per tant, això vol dir que potencialment podria fer una comparació per al segon element,
dues comparacions per al tercer element, i així successivament.
Així, el nombre total de passos és la suma dels enters d'1 a la longitud de la llista menys 1.
Podem representar això amb una suma.
>> No entrarem en sumes aquí, però resulta que aquesta suma és igual a
n (n - 1) sobre 2, que és equivalent n ^ 2/2 - n / 2.
Quan es parla de temps d'execució asimptòtic,
aquest n ^ 2 termini va a dominar aquest terme n.
Per tant, l'ordenació per inserció és Big O (n ^ 2).
Què passa si ens quedem ordenació per inserció en una llista ja ordenada.
En aquest cas, simplement s'havia acumulació de la porció ordenats d'esquerra a dreta.
Així que l'únic que necessita de l'ordre de n passos.
>> Això significa que l'ordenació per inserció té un rendiment millor dels casos de n,
que representem amb Ω (n).
I això és tot per tipus d'inserció,
només un dels molts algoritmes que es poden utilitzar per ordenar una llista.
El meu nom és Tommy, i això és CS50.
[CS50.TV]
Oh, no pots deixar que una vegada que s'iniciï.
Oh, ho vam fer - Boom! >>