Ordenament de bombolla

De WikiLingua.net

Taula de continguts

1 Descripció
2 Anàlisi
- 2.1 Rendiment en casos òptims
- 2.2 Conills i Tortugues
3 Implementaciones
4 En la pràctica
5 Vegi's també
6 Enllaços externs

[editar] Descripció

L'Ordenament de Bombolla (Bubble Sort en anglès) és un senzill algoritmo d'ordenament. Funciona revisant cada element de la llista que va a ser ordenada amb el següent, intercanviant-los de posició si estan en l'ordre equivocat. És necessari revisar diverses vegades tota la llista fins que no es necessitin més intercanvis, la qual cosa significa que la llista està ordenada. Aquest algoritmo obté el seu nom de la forma amb la qual pugen per la llista els elements durant els intercanvis, com si anessin petites "bombolles". També és conegut com el mètode de l'intercanvi directe.

Atès que solament usa comparacions per a operar elements, l'hi considera un algoritmo de comparació, sent el més senzill d'implementar.

Una manera simple d'expressar l'ordenament de bombolla en pseudocódigo és la següent:

Algoritmo Ordenament de bombolla
Procediment ${\it burbuja}\left(a_0,a_1,a_2,\ldots,a_{n-1}\right)$ Faci el següent: ${\it intercambio}\gets\mathbf{falso}$ Per a $i=0\,$ fins a $n-2\,$ faci el següent: Si $a_i>a_{i+1}\,$ llavors: $\left(a_i,a_{i+1}\right)\gets\left(a_{i+1},a_i\right)$ ${\it intercambio}\gets\mathbf{verdadero}$ Repeteixi mentre ${\it intercambio}=\mathbf{verdadero}$

La instrucció $\left(a_i,a_{i+1}\right)\gets\left(a_{i+1},a_i\right)$ significa que s'ha d'intercanviar el valor d'amb $a_i\,$ el de $a_{i+1}\,$ . L'algorítmo també pot ser expressat de manera equivalent com segueix:

Algoritmo Ordenament de bombolla
Procediment ${\it burbuja}\left(a_0,a_1,a_2,\ldots,a_{n-1}\right)$ Per a $i=0\,$ fins a $n-2\,$ faci el següent: Per a $j=i+1\,$ fins a $n-1\,$ faci el següent: Si $a_i>a_j\,$ llavors: $\left(a_i,a_j\right)\gets\left(a_j,a_i\right)$

Notar que:

Se suposa que els vectores que s'estan ordenant comencen en la posició zero (0) i acaben en la posició $n - 1$ .
L'ordenament es fa de menor a major, si es volgués fer al revés bastaria amb canviar el sentit de la comparació en les sentències si de cada algoritmo, és a dir, on posa '>' posar '<'.

[editar] Anàlisi

Ejemplo del ordenamiento de burbuja ordenando una lista de números aleatorios.

Exemple de l'ordenament de bombolla ordenant una llista de nombres aleatorios.

[editar] Rendiment en casos òptims

L'ordenament de bombolla té una complexitat Ω(n). Quan una llista ja està ordenada, l'ordenament de bombolla passarà per la llista una vegada, i trobarà que no hi ha necessitat d'intercanviar les posicions dels elements. Per tant, l'ordenament farà solament n comparacions i determinarà que la llista està completament ordenada. A més, usarà considerablement menys temps que О(n²) si els elements en la llista desordenada no estan massa lluny de la seva ubicació correcta.

[editar] Conills i Tortugues

La posició dels elements en l'ordenament de bombolla juguen un paper molt important en la determinació del rendiment. Els elements majors al principi de la llista són ràpidament moguts cap a a baix. En canvi, elements menors en el fons de la llista, es mouen a la part superior molt lentament. Això va portar a nomenar aquests elements conills i tortugues, respectivament.

Diversos esforços s'han realitzat per a eliminar les tortugues i millorar la velocitat de l'ordenament de bombolla. L'Ordenament per sacsejada és un bon exemple, encara que encara manté, en el pitjor dels casos, una complexitat O(n²). L'ordenament per combinació compara els elements primer en trossos grans de la llista, movent tortugues extremadament ràpid, abans de procedir a trossos cada vegada més petits per a alisar la llista. La seva velocitat promedio és comparable a algoritmos ràpids (i complexos) com l'ordenament ràpid

[editar] Implementaciones

A Continuació es veuran implementaciones de l'algoritmo d'ordenament de bombolla en distints llenguatges de programació

[editar] Visual Basic for Applications

Sub ORDENAR()
Dim X As Integer
Dim I As Integer
Dim i As Double
Dim j As Integer
 
X = 1
For I = 1 To 10
 Cells(I, 1) = Rnd
Next I
 
For I = 1 To 9
 For j = I + 1 To 10
 If Cells(I, 1) < Cells(j, 1) Then
 i = Cells(j, 1)
 Cells(j, 1) = Cells(I, 1)
 Cells(I, 1) = i
 End If
 
 Next j
 Next I
 
End Sub

[editar] C

void bubble(int *start, int *end) //Ordena un conjunt de nombres sencers de menor a major
  { 
    short fi;
    do
     {
      fi=0;
      for (int *i=start;i!=*end;i++) 
       {
         if (*i>*(i+1))
          {
           intercanvia(i, i+1);
           fi=1;
          }
        }
    }while (fi!=1);
  }

[editar] Python

def bubblesort(l):
    """Ordena la llesta l i la retorna."""
    for pasosIzq in range(len(l)-1, 0, -1):
        for indice in range(pasosIzq):
            if l[indice] < l[indice + 1]:
               l[indice], l[indice + 1] = l[indice + 1], l[indice]
    return l

[editar] Java

public void bubble(int [] a )/a) {
    for (int i=a.length-1; i>0; i--)
        for(int j=0; j<i; j++)
            if (a \[j] > a \[j+1]){
                int temp = a \[j]; 
                a \[j]= a \[j+1];
                a \[j+1]= temp;
            }
 
 
}

[editar] JavaScript

//Serveix per a odenamiento alfanumérico
for (var i=1; i<Vector.length;i++){
        for(var j=0;j<Vector.length-1;j++){
                if (Vector[j] > Vector[j+1]){
                        var temp = Vector[j];
                        Vector[j]= Vector[j+1];
                        Vector[j+1]= temp;
                }
        }
}

[editar] Perl

sub bubblesort {
    # Ordena la llista passada com argument per valor
    foreach my $i (    0 .. @_-2 ) {
    foreach my $j ( $i+1 .. @_-1 ) {
        @_[ $i, $j ] = @_[ $j, $i ] if $_[$i] > $_[$j] }}
}

[editar] COBOL

PERFORM ORDENAR-TAULA
            VARYING I FROM 1 BY 1
            UNTIL I > (TAM - 1)
    ...
 
ORDENAR-TAULA.
  PERFORM VARYING J FROM 1 BY 1 UNTIL J > (TAM - 1)
    IF REGISTRE-NAME(J + 1) < REGISTRE-NAME(J)
      MOVE REGISTRE(J) TO AUXILIAR
      MOVE REGISTRE(J + 1) TO REGISTRE(J)
      MOVE AUXILIAR TO REGISTRE(J + 1)
    END-IF
  END-PERFORM.

[editar] C#

int []a = new int[]{1,4,6,8,9,0};
        System.Console.WriteLine("Programa en C#");
        for (int i = 0; i < a.Length; i++)
          {
              for (int j = 0; j < a.Length-1; j++)
              {
                  if (a \[j] > a \[j+1])
                  {
                      int aux = a \[j];
                      a \[j] = a \[j+1];
                      a \[j+1] = aux;
                  }
              }
           }
           System.Console.WriteLine("Ara els Imprimeixo");
           for (int i = 0; i < a.Length; i++)
           { System.Console.WriteLine("Valor {0}: {1}", i + 1, a \[i]); }

[editar] PHP

function bubble_sort($array){
    $count = count($array);
    if ($count <= 0) return false;
    for($i=0; $i<$count; $i++){
        for($j=$count-1; $j>$i; $j–-){
            if ($array[$j] < $array[$j-1]){
                $tmp = $array[$j];
                $array[$j] = $array[$j-1];
                $array[$j-1] = $tmp;
             }
         }
     }
    return $array;
}

[editar] Pascal

Procedure BubleSort(var Sort:Array_integer);
 
Var
    a,s,Temp:integer;
Begin
 
 For a := 1 to 9 do
  For s := 0 to 8 do
   If (Sort[s] > Sort[s+1]) then
    Begin
     Temp:= Sort[s];
     Sort[s] := Sort[s+1];
     Sort[s+1] := temp;
    End;
 
End;

[editar] En la pràctica

A pesar que l'ordenament de bombolla és un dels algoritmos més senzills d'implementar, la seva ordre O(n²) ho fa molt ineficiente per a usar en llistes que tinguin més que un nombre reduït d'elements. Fins i tot entre els algoritmos d'ordenament d'ordre O(n²), altres procediments com l'Ordenament per inserció són considerats més eficients.

Donada el seu simplicidad, l'ordenament de bombolla és utilitzat per a introduir el concepte d'algoritmo, o d'algoritmo d'ordenament per a estudiants de ciències de la computación. Encara que alguns investigadors com Owen Astrachan han criticat a l'ordenament de bombolla i la seva popularitat en l'educació de la computación, recomanant que ja no ha de ser ensenyat.

L'ordenament de bombolla és asintóticamente equivalent, en temps d'execució amb l'Ordenament per inserció en el pitjor dels casos, però ambdós algoritmos difereixen principalment en la quantitat d'intercanvis que són necessaris. Resultats experimentals, com els descoberts per Astrachan han demostrat que l'ordenament per inserció funcionen considerablement millor fins i tot amb llestes aleatorias. Per aquesta raó, molts llibres d'algoritmos moderns eviten usar l'ordenament de bombolla, utilitzant en canvi l'ordenament per inserció.

L'ordenament de bombolla interactúa vagamente amb el maquinari de les CPU modernes. Requereix almenys el doble d'escriptures que l'ordenament per inserció, el doble de pèrdues de cache, i asintóticamente més predicció de salts. Diversos experiments, fets per Astrachan, d'ordenament de cadenes en Java, mostren que l'ordenament de bombolla és 5 vegades més lent que l'ordenament per inserció i 40% més lent que l'ordenament per selecció

[editar] Vegi's també

Algoritmo d'ordenament

[editar] Enllaços externs

Categoria: Algoritmos d'ordenament