Ordenamiento de Burbuja

BUBBLE SORT

EQUIPO 6: DAG, GAG, DG. AC, Dra. Elisa Schaeffer

INTRODUCCIONALGORITMO DE ORDENAMIENTO

Ordenamiento de listas de números en un orden específico

B U B B L E

S O R T

‘Clasificar’ o ‘sorting’

Quick sort Selection sort

Mergesort

(Método de Intercambio Directo)

BUBBLE SORT

Revisa cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado.

Este algoritmo obtiene su nombre de la forma con la que suben por la lista los elementos durante los intercambios, como si fueran pequeñas "burbujas". También es conocido como el método del intercambio directo.

[Funcionamiento]

Ordenamiento ascendente y descendente

9

28

12

5

33

2

52

52

33

28

12

9

5

2

2

5

9

12

28

33

52

Num[0]

Num[1]

Num[2]

Num[3]

Num[4]

Num[5]

Num[6]

Num[6]

Num[5]

Num[4]

Num[3]

Num[2]

Num[1]

Num[0]

Num[6]

Num[5]

Num[4]

Num[3]

Num[2]

Num[1]

Num[0]

Num (ordenado) Num (ordenado)

Num (desordenado)

Ord

en

asc

en

den

te

Ord

en

d

esc

en

den

te

4

8

7

10

5

Vector sin ordenar

Vector deinicio

Primera ite

ración

4

8

7

10

5

4

8

7

10

5

4

10

8

7

5

EJEMPLO…

Vector de fin de iteración

10

4

8

7

5

Vector de inicio

Vector deinicio

Segund

a iteració

n

10

4

8

7

5

10

8

7

4

5

10

8

7

4

5

EJEMPLO…

Vector de fin de iteración

Tercera

iteració

n

Cuarta

iteració

n

El vector ha quedado ordenado en 6

intercambios entre sus elementos (swap) y 4

iteraciones.

DIAGRAMA DE

FLUJO

#include<stdio.h>//programa para ordenar un vector de 20 elementos

#include<conio.h>

//......................COMPILADO EN TURBO C................

void main (){

int vectorx[20]={1,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2};

int mayor, menor;

int i, cambio;

printf("\n\nPrograma que da el vector ordenado en forma ascendente")

//PROCESO DE ORDENACION//

mayor=vectorx[0];

cambio=0;

for(i=1; i<=19; i++)

{ if(vectorx[i-1]>vectorx[i])

{cambio=1; //marcamos que hubo un cambio

menor=vectorx[i];

mayor=vectorx[i-1];

vectorx[i-1]=menor;

vectorx[i]=mayor;

//verificamos si debemos continuar en el for o salir para una nueva iteracion

if((cambio==0)&&(i==0))

break; //si ya llegamos a 19 y no hay cambio ya esta ordenado

else{

cambio=0; //inicializamos una nueva iteracion

mayor=vectorx[0];

i=1;

}

}//llave del primer if

}//llave del for

//¤¤¤¤¤¤¤¤¤¤¤¤SALIDA DEL VECTOR ORDENADO¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

for(i=0;i<=19;i++)

{printf("\n\nPosicion %d, es el Numero %d", i,vectorx[i]);}

getch();

clrscr();

}//fin de main

Clasificación de 20 elementos por el

método de la burbuja

EJEMPLO EJECUTADO

ANÁLISIS ASINTÓTICO

El ordenamiento de burbuja tiene una complejidad Ω(n²). Cuando una lista ya está ordenada, el método de ordenación por burbuja está forzado a pasar por toda la lista y hacer comparaciones, lo que hace que su complejidad sea cuadrática en el mejor de los casos, esto lo cataloga como el algoritmo mas ineficiente que existe aunque funciona bien cuando son pocos elementos.

BIBLIOGRAFIA http://es.wikipedia.org/wiki/Ordenamiento_de_burbuja PERRY, GREG c con ejemplos 1° edicion PRENTICE HALL

PEARSON EDUCACION Buenos Aires, 2000 SHANG,TONY Aprendiendo c en 24 horas PEARSON

EDUCACION, Mexico, 2001 AGUILAR, JOYANES IGNASIO ZAHONERO MARTINEZ

Programacion en c, MC GRAW-HILL Madrid, 2001 SCHILDT, HERBERT Manual de referencia C, cuarta edicion

OSBORNE, MC GRAW-HILL, Madrid, 2001 CEBALLOS, FRANCISCO JAVIER, Enciclopedia del lenguaje

C, ALFAOMEGA, Madrid, 1997 CAIRO, OSWALDO, Fundamentos de programacion, Piensa

en C, PEARSON-PRENTICE HILL, Mexico, 2006