Ordenación por Intercambio Directo

Método de la Burbuja. Bubble Sort. Métodos clásicos de ordenación. Estructuras de Datos

  • Enviado por: El remitente no desea revelar su nombre
  • Idioma: castellano
  • País: España España
  • 4 páginas
publicidad

CLASIFICACIÓN POR INTERCAMBIO DIRECTO.-

(METODO DE LA BURBUJA).

-Comparar pares de elementos contiguos

-Intercambiarlos si deben ordenarse

pase i=1 i=2 i=3 i=4 i=5 i=6 i=7 i=8

a[1]

44

06

06

06

06

06

06

06

a[2]

55

44

12

12

12

12

12

12

a[3]

12

55

44

18

18

18

18

18

a[4]

42

12

55

44

42

42

42

42

a[5]

94

42

18

55

44

44

44

44

a[6]

18

94

42

42

55

55

55

55

a[7]

06

18

94

67

67

67

67

67

a[8]

67

67

67

94

94

94

94

94

orden

inicial

descripción:

Hacemos varios pases sobre el arreglo, y en cada

recorrido desplazamos el elemento más pequeño

del conjunto restante hacia el extremo final del

arreglo, es decir:

Se comienza comparando a[1] con a[2]; si están

desordenados , se intercambian entre sí . A con-

tinuación se compara a[2] con a[3], intercambian-

dolos si están desordenados.

PROCEDURE intercambioDirecto;

VAR

i,j:index;

x:item;

BEGIN

FOR i:=2 TO n DO

FOR j:=n TO i BY -1 DO

IF a[j-1]>a[j] THEN

(*intercambia*)

x:=a[j-1];

a[j-1]:=a[j];

a[j]:=x;

END

END

END

END ordenación_por_burbuja

Análisis:

En la lista i representa el número de pasada y j indica el orden del elemento de la lista, es decir:

pase i=1

a[1]

44

a[2]

55

a[3]

12

a[4]

42

a[5]

94

a[6]

18

a[7]

06!

a[8]

67!

j=n-1

comparación 1, ningún intercambio

a[1]

44

44

a[2]

55

55

a[3]

12

12

a[4]

42

42

a[5]

94

94

a[6]

18

06!

a[7]

06

18!

a[8]

67

67

j=n-2

2ªcomparación ,un intercambio

pasada i=1

pase i=2 i=2 i=2 i=2 i=2 i=2 i=2 i=2

a[1]

44

44

44

44

44

44

06

06

a[2]

55

55

55

55

55

06

44

44

a[3]

12

12

12

12

06

55

55

55

a[4]

42

42

42

06

12

12

12

12

a[5]

94

94

06

42

42

42

42

42

a[6]

18

06

94

94

94

94

94

94

a[7]

06

18

18

18

18

18

18

18

a[8]

67

67

67

67

67

67

67

67

j=n

j=n-1

j=n-2

j=n-3

j=n-4

j=n-5

j=n-6

j=n-7

Es decir, por cada pasada se necesitan 7 comparaciones siendo 8 los elementos; el número de comparaciones totales viene dado

por;

Pasada Comparaciones

1 n-1

2 n-2

.. ..

n-1 1