Ordenació de bombolles vs. Ordenació de selecció
Bubble sort és un algorisme d'ordenació que funciona recorrent la llista per ordenar-se repetidament mentre es comparen parells d'elements adjacents. Si un parell d'elements està en l'ordre incorrecte, s'intercanvien per col·locar-los en l'ordre correcte. Aquesta travessa es repeteix fins que no calen més intercanvis. L'ordenació per selecció també és un algorisme d'ordenació, que comença per trobar l'element mínim a la llista i intercanviar-lo amb el primer element. Aquest procés es repeteix per a la resta de la llista col·locant els elements intercanviats en ordre.
Què és Bubble Sort?
Bubble sort és un algorisme d'ordenació que funciona recorrent la llista per ordenar-se repetidament mentre es comparen parells d'elements adjacents. Si un parell d'elements està en l'ordre incorrecte, s'intercanvien per col·locar-los en l'ordre correcte. Aquest recorregut es repeteix fins que no calen més intercanvis (el que significa que la llista està ordenada). Com que els elements més petits de la llista arriben a la part superior a mesura que una bombolla surt a la superfície, se li dóna el nom d'ordenació de bombolles. L'ordenació de bombolles és un algorisme d'ordenació molt senzill, però té una complexitat mitjana de temps de cas de O(n2) quan s'ordena una llista amb n elements. Per això, l'ordenació de bombolles no és adequada per ordenar llistes amb un gran nombre d'elements. Però a causa de la seva senzillesa, l'ordenació de bombolles s'ensenya durant les introduccions als algorismes.
Què és l'ordenació de selecció?
L'ordenació per selecció també és un altre algorisme d'ordenació que comença per trobar l'element mínim a la llista i intercanviar-lo amb el primer element. A continuació, es troba l'element mínim de la resta de la llista (des del segon element fins a l'últim element de la llista) i s'intercanvia amb el segon element. Aquest procés es repeteix per a la resta de la llista col·locant els elements intercanviats en ordre. Així, en l'ordenació per selecció, en qualsevol pas de l'algorisme, la llista es divideix en dues parts on una part conté elements ordenats i l' altra part conté elements no ordenats. A mesura que l'algorisme avança, la llista ordenada creix d'esquerra a dreta. L'ordenació de selecció també té una complexitat mitjana de temps de cas de O(n2). Per tant, tampoc és adequat per ordenar llistes grans.
Quina diferència hi ha entre l'ordenació de bombolles i l'ordenació de selecció?
Tot i que tant els algorismes d'ordenació de bombolles com d'ordenació de selecció tenen complexitats de temps de minúscules mitjanes d'O(n2), l'ordenació de bombolles gairebé sempre supera l'ordenació de selecció. Això es deu al nombre d'intercanvis que necessiten els dos algorismes (l'ordenació de bombolles necessita més intercanvis). Però a causa de la senzillesa de l'ordenació de bombolles, la mida del seu codi és molt petita. L'estabilitat és una altra diferència en aquests dos algorismes. Un algorisme d'ordenació estable és un algorisme d'ordenació que conserva l'ordre dels registres si la llista conté elements amb un valor igual. En aquest sentit, l'ordenació per selecció no és un algorisme estable, mentre que l'ordenació de bombolles és un algorisme estable.
