Ordenamiento de burbuja – Algoritmos de ordenamiento

Publicado por Andrea Navarro en

En este artículo se describe el algoritmo de ordenamiento de burbuja y su implementación en varios lenguajes.

El algoritmo de ordenamiento de burbuja es uno de los algoritmos de ordenamiento más sencillos aunque no es el más eficiente. Su simplicidad lo convierte en un algoritmo ideal para practicar programación.

Estabilidad: Estable

Método: Intercambio

Comparativo: Si

Uso de memoria: 1

Complejidad computacional:

Mejor caso: O(n)

Caso promedio: O(n²)

Peor caso: O(n²)

Algoritmo de ordenamiento de burbuja

Comenzamos con una lista de elementos no ordenados

Ordenamiento de burbuja

Tomamos  los primeros dos números y si no están ordenados se intercambian los lugares

Ordenamiento de burbuja

Se repite el proceso con los siguientes dos números

Ordenamiento de burbuja

El proceso continua hasta llegar al final

Ordenamiento de burbuja
Ordenamiento de burbuja

El último número ya queda ordenado por lo que en la siguiente iteración ya no se evalúa acortando el proceso

Ordenamiento de burbuja
Ordenamiento de burbuja
Ordenamiento de burbuja

En la tercera iteración no se evalúan los últimos dos valores

Ordenamiento de burbuja
Ordenamiento de burbuja

La cuarta iteración se finaliza sin que se haya realizado un intercambio por lo que el algoritmo termina

Ordenamiento de burbuja

Al finalizar el algoritmo tenemos como resultado la lista ordenadoOrdenamiento de burbuja

Código

C

#include<stdio.h>

#define SIZE 5


void mostrarLista(int *);

int main(int argc, char** argv){

	int lista[SIZE]={5,2,4,1,3};
	int n, l=SIZE,i,temp;

	mostrarLista(lista);


	do{
		n=0;
		//Recorrer la lista
		for(i=1;i<l;i++){
			//Verificar si los dos valores estan ordenados
			if(*(lista+i-1)>*(lista+i)){
				//Ordenar si es necesario
				temp=*(lista+i-1);
				*(lista+i-1)=*(lista+i);
				*(lista+i)=temp;
				n=i;
				mostrarLista(lista);
			}
		}
		l=n;
	}	while(n!=0);
	
}

//Función para mostrar estado de la lista

void mostrarLista(int *a){
  int i;
  for(i=0;i<SIZE;i++) printf("\t[%d]", *(a+i));
  printf("\n");
}

PHP

<?php
   
	$lista[0]=5;
	$lista[1]=2;
	$lista[2]=4;
	$lista[3]=1;
	$lista[4]=3;
	//Longitud de la lista
	$lon=count($lista);
	$l=$lon;
	
	mostrarLista($lista,$lon);
    do
    {
		$n=0;
		//Recorrer la lista
		for($i=1;$i<$l;$i++)
		{
			//Verificar si los dos valores estan ordenados
			if($lista[$i-1]>$lista[$i])
			{
				//Ordenar si es necesario
				$temp=$lista[$i-1];
				$lista[$i-1]=$lista[$i];
				$lista[$i]=$temp;
				$n=$i;
				mostrarLista($lista,$lon);
			}
		}
		$l=$n;
	}
	while($n!=0);
	
//Función para mostrar estado de la lista
function mostrarLista($lista,$lon)
{
	for($i=0;$i<$lon-1;$i++)
	{
		echo "$lista[$i] ";
	}
	echo "<br/>";
}

Pseudocódigo para PSeint

Proceso Burbuja
	Dimension lista[5];
	lista[1]=5;
	lista[2]=2;
	lista[3]=4;
	lista[4]=1;
	lista[5]=3;
	//Longitud de la lista
	lon=5;
	l=lon;
	
	mostrarLista(lista,lon);
    Hacer
		n=0;
		//Recorrer la lista
		Para i=2 Hasta l Con Paso 1 Hacer
			//Verificar si los dos valores estan ordenados
			Si lista[i-1]>lista[i]
				//Ordenar si es necesario
				temp=lista[i-1];
				lista[i-1]=lista[i];
				lista[i]=temp;
				n=i;
				mostrarLista(lista,lon);
			FinSi
			
		FinPara
		l=n;
	Hasta Que n=0;
FinProceso

//Función para mostrar estado de la lista
SubProceso mostrarLista(lista,lon)
	Para i=1 Hasta lon Con Paso 1 Hacer
		Escribir Sin Saltar lista[i] " ";
	FinPara
	Escribir "";
FinSubProceso

Espero que les sea de utilidad!


Andrea Navarro

- Ingeniera en Informática - Docente universitaria - Investigadora