EVP7

Algoritmo de ordenamiento

El ordenamiento es una labor común que realizamos continuamente. ¿Pero te has preguntado qué es ordenar? ¿No? Es que es algo tan corriente en nuestras vidas que no nos detenemos a pensar en ello. Ordenar es simplemente colocar información de una manera especial basándonos en un criterio de ordenamiento.

En la computación el ordenamiento de datos también cumple un rol muy importante, ya sea como un fin en sí o como parte de otros procedimientos más complejos. Se han desarrollado muchas técnicas en este ámbito, cada una con características específicas, y con ventajas y desventajas sobre las demás. Aquí voy a mostrarte algunas de las más comunes, tratando de hacerlo de una manera sencilla y comprensible.

 Ordenamiento Rápido (Quicksort)

^

^

Esta es probablemente la técnica más rápida conocida. Fue desarrollada por C.A.R. Hoare en 1960. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento (los algoritmos recursivos son en general más lentos que los iterativos, y consumen más recursos). El algoritmo fundamental es el siguiente:

Eliges un elemento de la lista. Puede ser cualquiera (en Optimizando veremos una forma más efectiva). Lo llamaremos elemento de división.

Buscas la posición que le corresponde en la lista ordenada (explicado más abajo).

Acomodas los elementos de la lista a cada lado del elemento de división, de manera que a un lado queden todos los menores que él y al otro los mayores (explicado más abajo también). En este momento el elemento de división separa la lista en dos sublistas. ejm

 Nombre Procedimiento: OrdRap

 Parámetros:

    lista a ordenar (lista)

    índice inferior (inf)

    índice superior (sup)

                  

    // Inicialización de variables

    1. elem_div = lista[sup];

    2. i = inf - 1;

    3. j = sup;

    4. cont = 1;

   

    // Verificamos que no se crucen los límites

    5. if (inf >= sup)

    6.      retornar;

   

    //  Clasificamos la sublista

    7. while (cont)

    8.      while (lista[++i] < elem_div);

    9.      while (lista[--j] > elem_div);

   10.      if (i < j)

   11.           temp = lista[i];

   12.           lista[i] = lista[j];

   13.           lista[j] = temp;

   14.      else

   15.           cont = 0;

  

   // Copiamos el elemento de división

   // en su posición final

   16. temp = lista[i];

   17. lista[i] = lista[sup];

   18. lista[sup] = temp;

  

   // Aplicamos el procedimiento

   // recursivamente a cada sublista

   19. OrdRap (lista, inf, i - 1);

   20. OrdRap (lista, i + 1, sup);

 Ordenamiento por Selección

^

Este algoritmo también es sencillo. 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.ejm

   1. for (i=0; i<TAM - 1; i++) 

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

    3.      temp = lista[i];

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

    5.      lista [pos_men] = temp;

Ordenamiento Burbuja (Bubblesort)

^

^

Este es el algoritmo más sencillo probablemente. Ideal para empezar. 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. ejm

    1. for (i=1; i<TAM; i++)

    2.      for j=0 ; j<TAM - 1; j++)

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

    4.                temp = lista[j];

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

    6.                lista[j+1] = temp;

EVP 6

MATRICES

Una matriz es un vector de vectores o un también llamado array bidimensional. La manera de declarar una matriz es C++ es similar a un vector:

int matrix[rows][cols];

int es el tipo de dato, matrix es el nombre del todo el conjunto de datos y debo de especificar el numero de filas y columnas.

Las matrices también pueden ser de distintos tipos de datos como char, float, double, etc. Las matrices en C++ se almacenan al igual que los vectores en posiciones consecutivas de memoria.

Usualmente uno se hace la idea que una matriz es como un tablero, pero internamente el manejo es como su definición lo indica, un vector de vectores, es decir, los vectores están uno detrás del otro juntos.

La forma de acceder a los elementos de la matriz es utilizando su nombre e indicando los 2 subíndices que van en los corchetes.

Si coloco int matriz[2][3] = 10; estoy asignando al cuarto elemento de la tercera fila el valor 10.

No olvidar que tanto filas como columnas se enumeran a partir de 0. Bueno y para recorrer una matriz podemos usar igualmente un bucle. En este caso usando 2 for:

for(int i = 0; i < rows; i++) {   for(int j = 0; j < cols; j++) {     matrix[i][j] = i % j;   } }