1. Algoritmos de Ordenación

Existen diferentes algoritmos de ordenación que se diferencian en su eficiencia. Un algoritmo será más eficiente cuanto más rápido sea y menos recursos consuma (memoria). Los datos a ordenar se pueden almacenar en memoria principal o en memoria masiva. Si los datos se guardan en listas y en pequeñas cantidades, se suelen almacenar de modo temporal en arrays y registros; estos datos se almacenan exclusivamente para tratamientos internos que se utilizan para gestión masiva de datos. Existen dos técnicas de ordenación fundamentales en gestión de datos: ordenación de listas y ordenación de archivos. Se conocen como métodos de ordenación internos o externos, según que los elementos a ordenar estén en la memoria principal (MP) o en la memoria secundaria (M. secundaria).

1.1. Ordenación por Burbuja

Es el menos eficiente. Los valores más pequeños “burbujean” gradualmente (suben) hacia la parte superior del array, mientras que los valores mayores bajan hacia la parte inferior del array. Requiere n-1 pasadas. Por cada pasada se comparan elementos adyacentes (parejas de elementos) y se intercambian sus valores cuando el primer elemento es mayor que el segundo. Al final de cada pasada, el elemento mayor ha “burbujeado” hasta la cola de la sublista actual. Por ejemplo, después de la pasada 0, la cola de la lista V[n-1] está ordenada y el frente de la lista permanece desordenado.

1.2. Ordenación por Intercambio

Es el algoritmo de ordenación más sencillo. Ordena los elementos de una lista o vector en orden ascendente. El algoritmo va comparando el elemento inferior de la lista con los restantes y efectuando intercambio de posiciones cuando el orden resultante de la comparación no sea el correcto.

1.3. Ordenación por Inserción

Se divide el array en dos partes, una ordenada y otra sin ordenar. Se coge el primer elemento de la parte no ordenada y se le hace avanzar hasta su lugar correspondiente dentro de la parte ordenada. Comienza considerando el primer elemento ordenado y continúa ordenando el segundo elemento respecto del primero, es decir, o se coloca delante o se queda donde está. Después se hace avanzar el índice que señala el primer elemento no ordenado. Se toma el tercero y se coloca en su lugar correcto respecto a los dos anteriores. Se hace avanzar el índice y se repite el proceso hasta que todos los elementos ocupen su lugar correcto, con lo cual el array quedará ordenado según las especificaciones de partida.

1.4. Ordenación por Shell

Compara elementos no contiguos, al contrario que el método de la burbuja, y separados por una gran distancia. Si los elementos no están en orden se intercambian. El algoritmo comienza especificando un intervalo o salto grande, comparando elementos separados por este intervalo y se intercambian si es necesario. El intervalo de partida se suele considerar igual a la mitad del intervalo total entre el primero y el último elemento, es decir, el término central es la primera referencia. Se analizan comparaciones entre elementos separados por ese intervalo.

1.5. Ordenación Rápida (Quicksort)

La ordenación rápida, inventada por C. Hoare, está considerada como el mejor algoritmo de ordenación disponible actualmente. Está basada en la ordenación por el método de intercambio. Implica la selección de un elemento de una lista y a continuación reordenar todos los elementos restantes en la sublista, de tal modo que todos los elementos que son más pequeños que el elemento dado se ponen en una sublista y todos los elementos que son más grandes que el elemento dado se ponen en una segunda lista.

2. Algoritmos de Búsqueda

2.1. Búsqueda Secuencial

Busca un elemento en una lista o vector utilizando un valor llamado clave. Los elementos del vector se examinan de forma secuencial. El algoritmo compara cada elemento del vector con la clave de búsqueda. Como el vector no está ordenado, en promedio el programa tendrá que comparar la clave de búsqueda con la mitad de los elementos del array.

2.2. Búsqueda Binaria

Aprovecha la ventaja de que los datos almacenados están ordenados. Compara cada elemento del array con la clave de búsqueda. Se sitúa la lectura en el centro de la lista y se comprueba si nuestra clave coincide con el valor del elemento central. Si no se encuentra el valor de la clave, se sitúa uno en la mitad inferior o superior del elemento central de la lista.

2.3. Búsqueda Binaria en Árboles

Si el árbol binario está ordenado, la búsqueda de un valor en un árbol se puede efectuar eliminando, cada vez que se examina un nudo, aquel de los dos subárboles que no puede contener el valor buscado (valores todos inferiores o todos superiores). A continuación, se examina la raíz del subárbol seleccionado y se elimina nuevamente uno de los subárboles de la raíz. El proceso termina cuando algún nudo coincida con el buscado o cuando se llegue a una hoja del árbol y no se pueda continuar. El siguiente ejemplo implementa la búsqueda utilizando la recursividad.