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