Ordenamiento de burbuja bidireccional – Algoritmos de ordenamiento

Publicado por Andrea Navarro en

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

El algoritmo de ordenamiento de burbuja bidireccional también llamado ordenamiento cocktail intenta mejorar el rendimiento del ordenamiento burbuja realizando el recorrido de comparación en ambas direcciones, de esta manera  se puede realizar más de un intercambio por iteración.

De la misma manera que el algoritmo de burbuja no se utiliza excepto para motivos pedagógicos por su falta de eficiencia pero sencillez de aplicació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²)

Ordenamiento de burbuja bidireccional

Comenzamos con una lista de elementos no ordenados

Ordenamiento de burbuja bidireccional

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

Ordenamiento de burbuja bidireccional

Se mueve un espacio hacia la derecha y se repite el proceso.

Ordenamiento de burbuja bidireccional

El proceso continua hasta llegar al final de la lista.

Ordenamiento de burbuja bidireccional
Ordenamiento de burbuja bidireccional

Al llegar al final a diferencia del ordenamiento de burbuja se repite el proceso en sentido inverso comenzando por el final de la lista hasta llegar al inicio.

Ordenamiento de burbuja bidireccional
Ordenamiento de burbuja bidireccional
Ordenamiento de burbuja bidireccional

Al terminar el proceso el último número y el primero ya quedan ordenados por lo que en la siguiente iteración ya no se evalúan acortando el proceso.

Ordenamiento de burbuja bidireccional
Ordenamiento de burbuja bidireccional
Ordenamiento de burbuja bidireccional

Al finalizar la segunda iteración se marcan como ordenados el primer y último número comparado.

No es posible realizar más iteraciones ya que no quedan dos números sin ordenar para comparar, por lo tanto el algoritmo termina.

Ordenamiento de burbuja bidireccional

Código

C

#include<stdio.h>

#define N 5

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

	int lista[N]={5,2,4,1,3};

	int inicioIndice=0;
	int finIndice=N-1;
	int i,aux,intercambio=0;

	//Recorrer la lista hasta que no haya números para ordenar
	while(inicioIndice<=finIndice){
		int nuevoPrimerIndice=finIndice,nuevoInicioIndice;
		int nuevoFinIndice=inicioIndice;
		
		//Ordenado hacia adelante
		for(i=inicioIndice;i<finIndice;i++){
			//Comparando valores
			if(*(lista+i)>*(lista+i+1)){
				//Intercambio valores
				aux=*(lista+i);
				*(lista+i)=*(lista+i+1);
				*(lista+i+1)=aux;
				//Marcar que ha ocurrido un intercambio
				intercambio=1;
				//Marcar último número ordenado al final de la *(lista
				nuevoFinIndice=i;
			}
		}
		
		if(!intercambio){
			//Si no se ha realizado ningún cambio salir de la iteracion
			break;
		}
		
		//Marcar el último número ordenado al final de la *(lista como final para no evaluarlo la siguiente iteración
		finIndice=nuevoFinIndice;
		intercambio=0;
		
		//Ordenado hacia atras
		for(i=finIndice;i>=inicioIndice;i--){
			//Comparando valores
			if(*(lista+i)>*(lista+i+1)){
				//Intercambio valores
				aux=*(lista+i);
				*(lista+i)=*(lista+i+1);
				*(lista+i+1)=aux;
				//Marcar que ha ocurrido un intercambio
				intercambio++;
				//Marcar último número ordenado al principio de la *(lista
				nuevoInicioIndice=i;
			}
		}
		
		if(!intercambio){
			//Si no se ha realizado ningún cambio salir de la iteracion
			break;
		}
		
		//Marcar el último número ordenado al principio de la *(lista como final para no evaluarlo la siguiente iteración
		inicioIndice=nuevoInicioIndice+1;
	}

	return 0;

}

PHP

<?php

$lista[0]=5;
$lista[1]=2;
$lista[2]=4;
$lista[3]=1;
$lista[4]=3;

$inicioIndice=0;
$finIndice=count($lista)-1;
$lon=count($lista);

//Recorrer la lista hasta que no haya números para ordenar
while($inicioIndice<=$finIndice)
{
	$nuevoPrimerIndice=$finIndice;
	$nuevoFinIndice=$inicioIndice;
	
	//Ordenado hacia adelante
	for($i=$inicioIndice;$i<$finIndice;$i++)
	{
		//Comparando valores
		if($lista[$i]>$lista[$i+1])
		{
			//Intercambio valores
			$aux=$lista[$i];
			$lista[$i]=$lista[$i+1];
			$lista[$i+1]=$aux;
			//Marcar que ha ocurrido un intercambio
			$intercambio=true;
			//Marcar último número ordenado al final de la lista
			$nuevoFinIndice=$i;
		}
	}
	
	if($intercambio == false)
	{
		//Si no se ha realizado ningún cambio salir de la iteracion
		break;
	}
	
	//Marcar el último número ordenado al final de la lista como final para no evaluarlo la siguiente iteración
	$finIndice=$nuevoFinIndice;
	$intercambio=false;
	
	//Ordenado hacia atras
	for($i=$finIndice;$i>=$inicioIndice;$i--)
	{
		//Comparando valores
		if($lista[$i]>$lista[$i+1])
		{
			//Intercambio valores
			$aux=$lista[$i];
			$lista[$i]=$lista[$i+1];
			$lista[$i+1]=$aux;
			//Marcar que ha ocurrido un intercambio
			$intercambio=true;
			//Marcar último número ordenado al principio de la lista
			$nuevoInicioIndice=$i;
		}
	}
	
	if($intercambio == false)
	{
		//Si no se ha realizado ningún cambio salir de la iteracion
		break;
	}
	
	//Marcar el último número ordenado al principio de la lista como final para no evaluarlo la siguiente iteración
	$inicioIndice=$nuevoInicioIndice+1;
	
}

Espero que les sirva!


¿Preguntas? ¿Comentarios?

Si tenés dudas, o querés dejarnos tus comentarios y consultas, sumate al grupo de Telegram de la comunidad JuncoTIC!
¡Te esperamos!


Andrea Navarro

- Ingeniera en Informática - Docente universitaria - Investigadora