Arreglos de Programacion Ordenamiento tipo Burbuja.

Proyecto Programación.

II Segundo trimestre.

Estudiantes:

Emanuel Villalobos

Nathaniel Córdoba

Sección 10-5

Ordenamiento tipo Burbuja.

Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor al siguiente que el que está en la siguiente posición se intercambian.

Vamos a  ver un ejemplo. Esta es nuestra lista:

Pseudocodigo

    1. for (i=1; i

    2.      for j=0 ; j

    3.           if (lista[j] > lista[j+1])

    4.                temp = lista[j];

    5.                lista[j] = lista[j+1];

    6.                lista[j+1] = temp;

4-3-5-2-1

Tenemos 5 elementos. Es decir, TAM toma el valor 5.

Comenzamos comparando el primero con el segundo, como 4 es mayor es mayor a 3 se intercambian, ahora tenemos que:

3-4-5-2-1

Ahora comparamos el segundo con el tercero 4 es menor que 5, así que no hacemos nada.

Continuamos con el tercero y el cuarto: 5 es mayor que dos, Intercambiamos y obtenemos que:

3-4-2-5-1

Comparamos el cuarto y el quinto: 5 es mayor que uno, se intercambian:

3-4-2-1-5

Repitiendo este proceso vamos obteniendo los siguientes resultados:

3-2-1-4-5

2-1-3-4-5

1-2-3-4-5

Ordenamiento por selección.

Consiste en lo siguiente:

• Buscas el elemento más pequeño de la lista.
• Lo intercambias con el elemento ubicado en la primera posición de la lista.
• Buscas el segundo elemento más pequeño de la lista.
• Lo intercambias con el elemento que ocupa la segunda posición en la lista.
• Repites este proceso hasta que hayas ordenado toda la lista.

Pseudocódigo

1. for (i=0; i

2.      pos_men = Menor(lista, TAM, i);

3.      temp = lista[i];

4.      lista[i] = lista [pos_men];

5.      lista [pos_men] = temp;

Un ejemplo

^

Vamos a ordenar la siguiente lista (la misma del ejemplo anterior:

4 - 3 - 5 - 2 - 1

Comenzamos buscando el elemento menor entre la primera y última posición. Es el 1. Lo intercambiamos con el 4 y la lista queda así:

1 - 3 - 5 - 2 - 4

Ahora buscamos el menor elemento entre la segunda y la última posición. Es el 2. Lo intercambiamos con el elemento en la segunda posición, es decir el 3. La lista queda así:

1 - 2 - 5 - 3 - 4

Buscamos el menor elemento entre la tercera posición  y la última. Es el 3, que intercambiamos con el 5:

1 - 2 - 3 - 5 - 4

El menor elemento entre la cuarta y quinta posición es el 4, que intercambiamos con el 5:

1 - 2 - 3 - 4 – 5

Ordenamiento Inserción

^

Este algoritmo también es bastante sencillo. ¿Has jugado cartas? ¿Cómo las vas ordenando cuando las recibes? Yo lo hago de esta manera: tomo la primera y la coloco en mi mano. Luego tomo la segunda y la comparo con la que tengo: si es mayor, la pongo a la derecha, y si es menor a la izquierda. Después tomo la tercera y la comparo con las que tengo en la mano, desplazándola hasta que quede en su posición final. Continúo haciendo esto, insertando cada carta en la posición que le corresponde, hasta que las tengo todas en orden. ¿Lo haces así tu también? Bueno, pues si es así entonces comprenderás fácilmente este algoritmo, porque es el mismo concepto.

Para simular esto en un programa necesitamos tener en cuenta algo: no podemos desplazar los elementos así como así o se perderá un elemento. Lo que hacemos es guardar una copia del elemento actual (que sería como la carta que tomamos) y desplazar todos los elementos mayores hacia la derecha. Luego copiamos el elemento guardado en la posición del último elemento que se desplazó.

Pseudocódigo:

   1. for (i=1; i

   2.       temp = lista[i];

   3.       j = i - 1;

   4.       while ( (lista[j] > temp) && (j >= 0) )

   5.            lista[j+1] = lista[j];

   6.            j--;

   7.       lista[j+1] = temp;

Un ejemplo

4 - 3 - 5 - 2 - 1

temp toma el valor del segundo elemento, 3. La primera carta es el 4. Ahora comparamos: 3 es menor que 4. Luego desplazamos el 4 una posición a la derecha y después copiamos el 3 en su lugar.

4 - 4 - 5 - 2 - 1

3 - 4 - 5 - 2 - 1

El siguiente elemento es 5. Comparamos con 4. Es mayor que 4, así que no ocurren intercambios.

Continuamos con el 2. Es menor que cinco: desplazamos el 5 una posición a la derecha:

3 - 4 - 5 - 5 - 1        

Comparamos con 4: es menor, así que desplazamos el 4 una posición a la derecha:

3 - 4 - 4 - 5 - 1

Comparamos con 3. Desplazamos el 3 una posición a la derecha:

3 - 3 - 4 - 5 - 1

Finalmente copiamos el 2 en su posición final:

2 - 3 - 4 - 5 - 1

El último elemento a ordenar es el 1. Cinco es menor que 1, así que lo desplazamos una posición a la derecha:

2 - 3 - 4 - 5 - 5

Continuando con el procedimiento la lista va quedando así:

2 - 3 - 4 - 4 – 5

2 - 3 - 3 - 4 – 5

2 - 2 - 3 - 4 – 5

1 - 2 - 3 - 4 - 5

...