>> [REPRODUCCIÓ DE MÚSICA]
DOUG LLOYD: Molt bé, així ordenament de bombolla és un algoritme
es pot utilitzar per ordenar un conjunt d'elements.
Fem una ullada a com funciona.
>> Així que la idea bàsica darrera ordenament de bombolla és això.
Generalment Volem avançar més alta elements valorats generalment a la dreta,
i baixar elements valorats generalment a l'esquerra, com era d'esperar.
Volem que les coses inferiors a estar a el principi, i les coses més elevades
a estar a l'extrem.
>> Com fem això?
Bé en el codi de pseudocodi, podríem dir, anem a
fixar un comptador de bescanvi a un valor diferent de zero.
Ja veurem què fem això en un segon.
I després repetim el següent procés fins que el comptador d'intercanvi és 0,
o fins que no fem canvis en absolut.
>> Restablir el comptador d'intercanvi d' 0 si no ho és ja 0.
Després, busquin en cada parell adjacent d'elements.
Si aquests dos elements són no en ordre, ells intercanviar,
i afegeix 1 al comptador d'intercanvi.
Si vostè està pensant en això abans de visualitzar-lo,
observi que aquest es mourà més baixa elements valuosos a l'esquerra
i més alt elements a la dreta valorada, fent amb eficàcia el que volem fer,
que és moure aquests grups d'elements en aquesta forma.
Anem a visualitzar com aquest podria semblar utilitzant la nostra gamma
que utilitzem per provar aquests algoritmes.
Tenim una gran varietat classificar aquí de nou, indicat per tots els elements
estant en vermell.
I vaig tornar el meu comptador d'intercanvi a un valor diferent de zero.
Jo vaig triar arbitràriament negatiu 1-- no és 0.
Volem repetir aquest procés fins que el comptador d'intercanvi és de 0.
Per això em vaig posar el meu permuta comptador a algun valor diferent de zero,
perquè en cas contrari la comptador d'intercanvi seria 0.
Ni tan sols podríem començar el procés de l'algorisme.
Així que de nou, els passos són-- restablir el comptador d'intercanvi
a 0, a continuació, cerqueu a cada costat parell, i si estan fora de servei,
intercanviar-los, i afegir 1 al taulell d'intercanvi.
Així que anem a començar aquest procés.
Així que el primer que fem és ens vam posar al taulell d'intercanvi a 0,
i després començar a cercar en cada parell adjacent.
>> Així que primer començar a buscar a les 5 i 2.
Veiem que estan fora de Ordre i així que els swap.
I afegim 1 al comptador d'intercanvi.
Així que ara el nostre comptador d'intercanvi és 1, i 2 i 5 han estat commutada.
Ara repetim el procés de nou.
>> Ens fixem en el següent parell adjacent, 5 i 1-- estan també fora d'ordre,
així que els swap i afegim 1 al comptador d'intercanvi.
Llavors ens fixem en 5 i 3.
Ells estan fora de servei, de manera que intercanvien ells i afegim 1 al comptador d'intercanvi.
Llavors ens fixem en 5 i 6.
Estan en ordre, així que en realitat no necessitarà canviar res aquesta vegada.
Llavors ens fixem en 6 i 4.
Són també fora de servei, així que intercanvien ells i afegim 1 al comptador d'intercanvi.
>> Ara noti el que ha passat.
Hem passat 6 de tot el camí fins al final.
Així que en la selecció d'espècie, si tens vist aquest vídeo, el que vam fer va ser
Acabem canviant la els elements més petits de la construcció
la matriu ordenada essencialment de esquerra a dreta, de menor a major.
En el cas d'ordenament de bombolla, si som seguint aquest algorisme en particular,
estem en realitat serà la construcció la matriu ordenada de dreta
a esquerra, de major a menor.
Hem bombolleig eficaçment 6, la valor més gran, tot el camí fins al final.
>> I així podem ara declarar que això es va solucionar,
i en el futur iterations-- passant per la matriu nou--
no hem de considerar 6 més.
Només hem de considerar els elements sense classificar
quan estem veient parells adjacents.
Així que hem acabat un sol passar a través d'ordenament de bombolla.
Així que ara tornem a la pregunta, repetir fins que el comptador d'intercanvi és 0.
Bé el comptador d'intercanvi és 4, per la qual cosa anem
seguir repetint aquest procés de nou.
>> Anem a zero el comptador d'intercanvi a 0, i buscar en cada parell adjacent.
Així que vam començar amb 2 i 1-- són fora de servei, de manera que els intercanviem
i sumem 1 al comptador d'intercanvi.
2 i 3, estan en ordre.
No necessitem fer res.
3 i 5 són en ordre.
No necessitem fer res allà.
>> 5 i 4, estan fora d'ordre, de manera que
necessari per intercanviar i afegir 1 al comptador d'intercanvi.
I ara ens hem mogut 5, el següent element més gran,
fins al final de la porció sense classificar.
Així que ara podem anomenar a això part de la porció ordenats.
>> Ara vostè està buscant en el pantalla i probablement pot dir,
igual que jo, que la matriu es classifica en aquest moment.
Però no podem provar que encara.
No tenim una garantia que està ordenada.
Però aquí és on el bescanvi comptador que va entrar en joc.
>> Així que hem completat una passada.
El comptador d'intercanvi és de 2.
Així que repetirem aquest procés de nou,
repetir fins que el comptador d'intercanvi és 0.
Restablir el comptador d'intercanvi a 0.
Així que anem a restablir-la.
>> Ara mira cada parell adjacent.
Aquest és la fi, 1 i 2.
2 i 3 són en ordre.
3 i 4 són en ordre.
Així que en aquest punt, notem que hem completat buscant en cada parell adjacent,
però el comptador d'intercanvi continua sent 0.
>> Si nosaltres no hem de canviar qualsevol element, llavors
ha d'estar en ordre, per virtut d'aquest procés.
I així una eficiència de classes, que els científics de la computació ens encanta,
està ara podem Declarem tota la matriu ha de
ser resolt, perquè no vam fer haver de canviar cap element.
Això és bastant agradable.
>> Quin és el pitjor dels casos escenari amb la bombolla del tipus?
En el pitjor dels casos la matriu és per tal completament inversa,
i així tenim que la bombolla de cada dels grans elements de tot
el camí a través de la matriu.
I efectivament tenim també bombolla de tots els petits elements de retorn
tot el camí a través de la matriu, també.
Així cada un dels n elements ha de moure a través de tots els altres elements n.
Així que aquest és el pitjor dels casos.
En el millor dels casos escenari però, això és
lleugerament diferent d'ordenació per selecció.
La matriu és ja ordenats quan anem a.
Nosaltres no hem de fer cap swaps en la primera passada.
Així que pot ser que haguem de mirar almenys elements, oi?
No hem de repetir aquest processar un nombre de vegades.
>> Llavors, què vol dir això?
Quin és el pitjor dels casos d'ordenament de bombolla, i el que és
el millor dels casos per a l'ordenació de bombolla?
Sabia vostè endevina això?
En el pitjor dels casos vostè ha de repetir a través de tots els n elements n vegades.
Així que el pitjor dels casos és N al quadrat.
>> Si la matriu és perfectament ordenada, però, només es
cal mirar cada dels elements d'una vegada.
I si el comptador d'intercanvi segueix sent 0, es pot dir que aquesta sèrie està ordenada.
I així, en el millor dels casos, es tracta de en realitat millor que la selecció
sort-- és l'omega de n.
>> Sóc Doug Lloyd.
Això és CS50.