Ordenació de bombolles vs. Ordenació d'inserció
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 inserció també és un algorisme d'ordenació, que funciona inserint un element a la llista d'entrada a la posició correcta en una llista que ja està ordenada. Aquest procés s'aplica repetidament fins que s'ordena la llista.
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ó d'inserció?
L'ordenació per inserció és un altre algorisme d'ordenació, que funciona inserint un element a la llista d'entrada a la posició correcta d'una llista (que ja està ordenada). Aquest procés s'aplica repetidament fins que s'ordena la llista. En l'ordenació d'inserció, l'ordenació es realitza in situ. Per tant, després de la i-iteració de l'algorisme, les primeres entrades i+1 de la llista s'ordenaran i la resta de la llista no s'ordenarà. A cada iteració, s'agafarà el primer element de la part no ordenada de la llista i s'inserirà al lloc correcte de la secció ordenada de la llista. L'ordenació d'inserció té una complexitat mitjana de temps de cas de O(n2). Per això, l'ordenació per inserció tampoc és adequada per ordenar llistes grans.
Quina diferència hi ha entre l'ordenació de bombolles i l'ordenació d'inserció?
Tot i que tant els algorismes d'ordenació de bombolles com d'inserció tenen complexitats de temps de minúscules mitjanes d'O(n2), l'ordenació de bombolles és gairebé sempre superada per l'ordenació d'inserció. 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. També hi ha una variant d'ordenació d'inserció anomenada shell sort, que té una complexitat temporal de O(n3/2), que permetria utilitzar-la pràcticament. A més, l'ordenació per inserció és molt eficient per ordenar llistes "gairebé ordenades", en comparació amb l'ordenació de bombolles.
