[Powered by Google Translate] TOMMY: Anem a fer una ullada a l'ordenació per selecció, un algorisme
per a la presa d'una llista de nombres i classificar-les.
Un algorisme, recordi, és simplement un pas a pas
procediment per dur a terme una tasca.
La idea bàsica darrere de l'ordenació per selecció é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
Unsorted porció a la porció ordenats fins que finalment la
tota la llista s'organitza.
Així que aquí hi ha una llista de sis números -
23, 42, 4, 16, 8, i 15.
En aquest moment tota la llista es considera sense ordenar.
Tot i que un nombre com 16 pot estar ja en la seva correcta
ubicació, el nostre algorisme no té manera de saber que fins que el
tota la llista s'organitza.
Així que considerarem cada nombre que es Unsorted fins d'ordenar
nosaltres mateixos.
Sabem que volem que la llista sigui en ordre ascendent.
Així que anem a voler construir la porció ordenada de la nostra llista
d'esquerra a dreta, el més petit al més gran.
Per fer-ho, haurem de trobar l'element mínim sense classificar
i el situen a l'extrem de la part ordenats.
Atès que aquesta llista no està ordenada, l'única manera de fer-ho és
veure tots els elements de la part sense classificar, recordant
quin element és el més baix i comparant
cada element a això.
Així que el primer que veurem el 23.
Aquest és el primer element que hem vist, així que vaig a recordar
com el mínim.
A continuació veurem 42.
42 és més gran que 23, de manera que 23 continua sent el mínim.
El següent és el 4, que està a menys de 23, així que recordarem 4
com el nou mínim.
Següent és 16, que és major que 4, de manera 4
encara és el mínim.
8 és major que 4, i 15 és major que 4, per la qual cosa ha de ser 4
l'element més petit sense classificar.
Així que tot i que com a éssers humans podem veure immediatament que el 4 és
l'element mínim, el nostre algorisme té a veure
cada element sense classificar, fins i tot després que hagis trobat el 4 - el
element mínim.
Així que ara que hem trobat l'element mínim, 4, anem a voler
per moure'ls a la part de la llista ordenada.
Atès que aquest és el primer pas, això vol dir que volem posar 4 a
el principi de la llista.
En aquest moment 23 es troba al principi de la llista, de manera
canviarem el 4 i 23 de la.
Així que ara la llista són aquestes.
Sabem que 4 ha d'estar en la seva ubicació final, perquè és
tant l'element més petit i l'element al principi
de la llista.
Així que això significa que no sempre hagi de moure de nou.
Així que repetirem aquest procés per afegir un element més a la
ordenats part de la llista.
Sabem que no hem de mirar a la 4, perquè és
ja ordenats.
Així que podem començar en el 42, que recordarem com el
element mínim.
Així que la propera veurem el 23, que és inferior a 42, de manera que
Recordo 23 és el nou mínim.
A continuació veiem el 16 que és menor que 23, per
16 és el nou mínim.
Ara ens fixem en el 8, que és menys de 16, de manera
8 és el nou mínim.
I finalment 8 és menor que 15, pel que sabem que 8 és un mínim
element sense classificar.
Així que això significa que hauríem d'afegir 8 al ordenar
part de la llista.
En aquest moment 4 és l'únic element classificat, pel que volem col · locar
el 8 al 4.
Atès que 42 és el primer element en la part no seleccionada de la
llista, anem a voler canviar el 42 i el 8.
Així que ara la llista són aquestes.
4 i 8 representen la part ordenada de la llista, i el
nombres restants representen la Unsorted
part de la llista.
Així que continuarem amb una altra iteració.
Comencem amb 23 aquesta vegada, ja que no cal buscar en
el 4 i el 8 ja perquè no tenen
ja s'ha solucionat.
16 és menor que 23, pel que recordarà
16 com el nou mínim.
16 és menor que 42, però 15 és menor que 16, per la qual cosa ha de ser 15
l'element Unsorted mínim.
Així que ara volem intercanviar el 15 i el 23 de
ens donen aquesta llista.
La part ordenada de la llista es compon de 4, 8 i 15, i
aquests elements estan encara sense classificar.
Però dóna la casualitat que el següent element sense classificar, 16,
ja està ordenat.
No obstant això, no hi ha manera que el nostre algorisme per saber que el 16 per
ja es troba en la seva ubicació correcta, de manera que encara hem de
repetir exactament el mateix procés.
Així veiem que 16 és menor que 42, i 16 és menor que 23, per
16 ha de ser l'element mínim.
És impossible canviar aquest element amb si mateix, perquè puguem
simplement deixi en aquest lloc.
Així que hem de passar un més del nostre algorisme.
42 és més gran que 23, per la qual cosa ha de ser el 23
element Unsorted mínim.
Quan canviï el 23 i 42 de la, acabem amb el nostre últim
llista ordenada -
4, 8, 15, 16, 23, 42.
Sabem 42 ha d'estar en el lloc correcte, ja que és la
únic element a l'esquerra, i que és una espècie de selecció.
Ara anem a formalitzar nostre algorisme amb alguns
pseudocodi.
En la línia un, podem veure que necessitem per integrar més
cada element de la llista.
Excepte l'últim element, ja que l'element 1
llista ja està ordenada.
En la segona línia, considerem que el primer element de la Unsorted
part de la llista per ser el mínim, com ho vam fer amb la nostra
exemple, així que tenim alguna cosa per comparar.
La línia tres s'inicia un segon bucle en què iterar sobre
cada element sense classificar.
Sabem que després d'i iteracions, la porció ordenats
de la llista ha de tenir i elements en ella, ja que cada pas
classe un element.
De manera que l'element no seleccionats ha d'estar en la posició i + 1.
En la línia quatre, es compara aquest element al mínim
element que hem vist fins ara.
Si l'element actual és menor que el mínim
element, llavors recordem aquest element com la nova
mínim en la línia cinc.
Finalment, en les línies sis i set, canviem el mínim
element amb l'element sense classificar primer, de manera
afegir a la porció de la llista ordenada.
Quan tenim un algorisme, un tema crític
nosaltres de programador fa temps em portarà?
En primer lloc, vaig a fer la pregunta quant de temps es necessita perquè aquesta
algoritme per executar-se en el pitjor dels casos?
Recordem que representem aquesta carrera
temps amb la notació O gran.
Per tal de determinar l'element Unsorted mínim, es
essencialment havien de comparar cada element de la llista per
cada altre element a la llista.
Intuïtivament, això sona com una junta d'operació núm al quadrat.
Quant al nostre pseudocodi, també tenim un bucle niat dins
altre bucle, que en realitat sona com una junta
d'operació n al quadrat.
No obstant això, recordeu que no hi havia necessitat de mirar per sobre de la
llista completa per determinar l'element Unsorted mínim?
Quan vam saber que el 4 es classifiquen, per exemple, no ens
necessitem veure de nou.
El mateix passa amb aquest menor és el temps d'execució?
Per a la nostra llista de longitud 6, havíem de fer cinc
comparacions per al primer element, quatre comparacions per
el segon element, i així successivament.
Això significa que el nombre total de passos és la suma dels
els nombres 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 vegades
n menys 1 sobre 2.
O de forma equivalent, en al quadrat sobre 2 menys n sobre 2.
Quan es parla de temps d'execució asimptòtic, aquest terme al quadrat n
va a dominar aquest terme n.
Així tipus de selecció és O de n al quadrat.
Recordem que en el nostre exemple, classificar selecció segueix sent necessari per
comprovar si un nombre que ja es va solucionar
necessària per ser mogut.
Així que això vol dir que si ens trobem amb una mena de selecció sobre ja
llista ordenada, es requeriria el mateix nombre de passos com es
ho faria quan s'executa sobre una llista completament sense classificar.
Així que tipus de selecció té un acompliment millor dels casos quadrat de n,
que representem amb omega n al quadrat.
I això és tot per tipus de selecció.
Només un dels molts algoritmes que puguem
utilitzar per ordenar una llista.
El meu nom és Tommy, i això és CS50.