[REPRODUCCIÓ DE MÚSICA] DOUG LLOYD: Selecció tipus és un algoritme que, com era d'esperar, ordena un conjunt d'elements. I algoritme de recuperació és un conjunt pas a pas d'instruccions per completar una tasca. 

En la selecció ordenar la idea bàsica és la següent, trobar l'element més petit i sense classificar afegir al final de la llista ordenada. Efectivament el que això fa és construir una llista ordenada, un element a la vegada. Trencant amb què pseudocodi podríem afirmar que aquest algorisme la següent, repetir això fins sense elements no classificats romanen. Feu una recerca entre els no seleccionats dades per trobar el valor més petit, a continuació, canviar el valor més petit amb el primer element de la part sense classificar. 

Es pot ajudar a visualitzar això, així que anem a fer una ullada a això. Així que això, sostinc, és una array sense classificar i tinc s'indica mitjançant la indicació que tots dels elements són de color vermell, que encara no estan ordenats. Aquest és el sencer part no seleccionada de la matriu. 

Així que anem a anar a través dels passos de ordenació per selecció per ordenar aquesta matriu. Així que de nou, repetirem fins que no romanen sense classificar elements. Buscarem a través de la dades per trobar el valor més petit, i després canviar aquest valor amb el primer element de la part sense classificar. 

Ara, de nou, tot el matriu és la part sense classificar. Tots els elements són de color vermell sense classificar. Així que busquem a través i ens trobem amb el valor més petit. Comencem pel principi, anem fins al final, ens trobem amb el valor més petit és, un. Així que aquesta és la primera part. I després la segona part, intercanviar aquest valor amb el primer element de la part sense classificar, o el primer element de vermell. 

En aquest cas que seria cinc, així que intercanviem 01:05. Quan fem això, podem veiem visualment que hem mogut l'element valorat més petit de la matriu, al principi. Efectivament classificació d'aquest element. 

I pel que podem confirmar de fet i l'estat que un, es classifica. I el que anem a indicar la part ordenats de la nostra matriu, pintant de blau. 

Ara només repetim el procés de nou. Busquem a través de la part no seleccionada de la matriu per trobar l'element més petit. En aquest cas, és dues. 

Intercanviem que amb la primera element de la part sense classificar. En aquest cas dos també passa a ser el primer element de la part sense classificar. Així que intercanviem 2 amb si mateix, que en realitat només deixa 02:00 on està, i està ordenada. Continuant, busquem a través per trobar l'element més petit. Són les tres. Intercanviem amb el primer element, que és cinc. I ara tres està ordenat. 

Busquem a través de nou, i ens trobar l'element més petit és de quatre. Intercanviem amb el primer element de la part sense classificar, i ara 4 es va solucionar. 

Trobem que 5 és l'element més petit. Intercanviem amb el primer element de la part sense classificar. I ara de cinc s'ordena. 

I després, finalment, la nostra part sense classificar consisteix d'un sol element, així de buscar a través de i ens trobem amb què sis és el més petit, i de fet, únic element. I llavors podem afirmar que s'ordena. I ara hem canviat la nostra gamma de ser completament sense classificar en vermell, que ordenats per complet en blau, mitjançant la selecció de classificació. 

Quin és el pitjor dels casos aquí? Bé, en el pitjor cas, hem de mirar per sobre de tots els elements de la matriu a trobar l'element més petit sense classificar, i hem de repetir aquest procés n vegades. Un cop per cada element de la matriu perquè només en aquest algoritme, ordenar un element a la vegada. 

Quin és el millor dels casos? Bé, és exactament el mateix, no? De fet, tenim que segueixen pas a pas cada element de la matriu per tal de confirmar que es tracta, de fet, l'element més petit. 

Així el pitjor temps d'execució cas, haver de repetir un procés n vegades, una vegada per a cada un de n elements. I en el millor dels casos, hem de fer el mateix. 

Així que pensant en tornar a la nostra caixa d'eines de la complexitat computacional, ¿Què creus que és el pitjor runtime cas per a la selecció d'una espècie? Què creus que és el millor runtime cas per a la selecció d'una espècie? 

Sabia vostè endevina O gran de n al quadrat, i Big Omega de n al quadrat? Vostè tindria raó. Aquells són, de fet, la pitjor dels casos i la millor ratxa cas vegades, per a la selecció d'espècie. 

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