Ordenamiento de burbuja – Algoritmos de ordenamiento

Publicado por Andrea Navarro en

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: on

Caso promedio: n2

Peor caso: n2

 

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 en 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");
}

 

Código en 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