Algotimos

Ordenamiento Burbuja

^

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

void burbuja(int x[]){

int i, j, aux;

for (i = 0; i < x.length; i++)

{

for (j = 0; j
{

if (x[j] > x[j+1])

{

aux = x[j];

x[j] = x[j+1];

x[j+1] = aux;

} }

}

for (i = 0; i < x.length; i++){//AQUI SE RECORRE EL ARREGLO

printf(x[i] + " ");//AQUI SE IMPRIME EL ARREGLO YA ACOMODADO}

}

Ejemplo

4 - 3 - 5 - 2 - 1

Tenemos 5 elementos. Es decir, TAM toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos:

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 2. Intercambiamos yobtenemos:

3 - 4 - 2 - 5 - 1

Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente:

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

Tiempo de Ejecución

El ciclo interno se ejecuta n veces para una lista de n elementos. El ciclo externo también seejecuta n veces. Es decir, la complejidad es n * n = O(n2). El comportamiento del caso promedio depende del orden de entrada de los datos, pero es sólo un poco mejor que el del peor caso, y sigue siendo O(n2).

Ordenamiento por Selección.

Este 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.

void OrdenarPorSeleccionRecursivo(int Numeros[], int N) {
   int aux, i, PosMayor;

   if (N > 1) {
      /* Elige el mayor */
      PosMayor = 0;  /* Supone que el mayor es el primero */      for (i=1; i Numeros[PosMayor])
            PosMayor = i;

      /* Se lleva a cabo el intercambio */
      aux = Numeros[N - 1];
      Numeros[N - 1] = Numeros[PosMayor];
      Numeros[PosMayor] = aux;

      /* Llamado recursivo a la funcion con el subvector de N-1 elementos */
      OrdenarPorSeleccionRecursivo(Numeros, N - 1);
   }
}

Ejemplo

4 - 3 - 5 - 2 - 1

Comenzamosbuscando 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 (sí,adivinaste :-D) 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

Tiempo de Ejecución:

El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Estealgoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad promedio es también O(n2).

Ordenamiento por Inserción

En este tipo de algoritmo los elementos que van a ser ordenados son considerados uno a la vez. Cada elemento es INSERTADO en la posición apropiada con respecto al resto de los elementos ya ordenados.

void insertionSort(int...

Leer documento completo

Regístrate para leer el documento completo.