En programación existen tres operaciones importantes: ordenación, búsqueda y mezcla. Se trata de unas técnicas importantes utilizadas en los lenguajes de programación y en la cotidianidad de las personas.

La ordenación o clasificación es la operación de organizar los datos de acuerdo con criterios específicos, de forma creciente o decreciente, para datos numéricos o alfabéticamente para cadena de caracteres alfanuméricos.

Por su parte, la búsqueda se refiere a la operación de encontrar un valor en una posición entre un conjunto de valores. En ésta se identifican dos técnicas: la lineal y secuencial.

En la génesis de la computación el problema de la ordenación ha demandado un tiempo considerable en investigación y los matemáticos han desarrollado los algoritmos como una solución optima y eficiente. Por lo anterior, es que el estudiante debe desarrollar esta competencia, ya que le permitirá solucionar problemas de búsqueda y ordenamiento. Así mismo, el estudiante, al finalizar esta unidad estará en condiciones de responder a las siguientes preguntas:

• ¿Qué es ordenamiento y como se aplica?
• ¿Cuáles son las técnica de ordenamiento?
• ¿Cuándo utilizar la recursividad?
• ¿Cuándo no usar la recursividad?
• ¿Cuáles son los problemas que se puede incurrir al utilizar algoritmos recursivos?

Material de apoyo

Objetivo general

Desarrollar los algoritmos que permitan la implementación de ordenamiento y búsqueda.

Objetivos específicos

• Seleccionar los algoritmos de búsqueda y complejidad para los algoritmos de búsqueda.
• Construir algoritmos de ordenamiento para las técnicas por selección, inserción, intercambio directo, Shell, montículos y ordenamiento rápido.

Se considera que la solución de un problema es eficiente si el tiempo de ejecución está acotado por una función polinomial; es decir, por O(n^k). Así, se le considera un problema fácil, pero en caso de que su tiempo de ejecución es mayor a la función polinomial, se le considera difícil.

Los tiempos de ejecución más usados se ordenan de más rápidos a más lentos, así: Q(1) (constante), Q(log n) (logarítmico), Q([log n]k) (polilogarítmico), Q(n) (lineal), Q(n log n), Q(n²) (cuadrado), Q(n³) (cúbico), Q(n^k) (polinomial), Q(kⁿ) (exponencial), Q(nn) y Q(n!) (factorial) donde n es la entrada y k una constante.

En la métrica del uso de los recursos computacionales, para la ejecución de un algoritmo con relación al tamaño de las entradas T(n), se consideran diversos componentes como:

• El costo del tiempo de las personas que desarrollan, mantienen y usan el programa.
• El costo de la ejecución del programa (eficiencia del programa).
• La complejidad de implementación del o los algoritmos aplicados.

La medición de tiempo de ejecución se hace por: mejor caso, peor caso, caso promedio, análisis probabilístico y análisis amortizado.

La búsqueda consiste en la recuperación de información de la manera más rápida posible y radica en encontrar un elemento de una lista o secuencia de elementos ordenados o desordenados.

Por lo general la búsqueda puede ser:

• Búsqueda interna: los elementos se encuentra en la memoria principal (RAM).
• Búsqueda externa: los elementos se encuentran almacenados en memoria secundaria.

Adicionalmente, existen cuatro tipos de búsqueda que facilitan el rescate de los datos de manera eficiente.

Es un método aplicado a un conjunto de elementos según un criterio definido, ya sea numérico, alfanumérico o por fecha, con el fin de simplificar su recuperación posterior.

Se clasifican en:

• Búsqueda interna: los elementos se encuentra en la memoria principal (RAM).
• Búsqueda externa: los elementos se encuentran almacenados en memoria secundaria.

Así mismo existen diversos tipos:

• Ordenamiento por selección: basa su ejecución en que cada vez que se mueve un elemento, se lleva a su posición correcta.
• Ordenamiento por inserción: conocido como el método de la baraja por ser el método habitual de los jugadores de carta.
• Ordenamiento por intercambio directo (burbuja): comparar pares de elementos contiguos y se intercambian si deben ordenarse.
• Ordenamiento Shell¹: es una versión mejorada del método de inserción directa.
• Ordenamiento por montículos: conocido por Heapsort, es el método mas eficiente de los métodos de ordenación que trabaja con árboles.
• Ordenamiento rápido: (Quicksort en inglés), basado en la técnica "divide y vencerás", que permite ordenar n elementos en un tiempo proporcional a n log n.

Material de apoyo

El ordenamiento por selección basa su ejecución en que cada vez que se mueve un elemento, se lleva a su posición correcta. Al examinar todos los elementos, se localiza el más pequeño y se sitúa en la primera posición.

Luego se ubica el menor de los restantes y se sitúa en la segunda posición. Se procede de manera similar sucesivamente hasta que quedan dos elementos.

Entonces se localiza el menor y se sitúa en la penúltima posición y el último elemento, que será el mayor de todos, ya queda automáticamente colocado en su posición correcta.

El tiempo de ejecución viene determinado por el número de comparaciones, las cuales son independientes del orden original de los elementos, el tiempo de ejecución es Q(n).

Conocido como el método de la baraja por ser el método habitual de los jugadores de carta. Consiste en tomar elemento a elemento e irlo insertando en su posición correcta de manera que se mantenga el orden de los elementos ya organizados.

Para ello, se toma el primer elemento, después se toma el segundo y se inserta en la posición adecuada para que ambos estén ordenados, se toma el tercero y se vuelve a insertar en la posición adecuada para que los tres estén ordenados, y así sucesivamente:

1. Se debe suponer el primer elemento ordenado.
2. Desde el segundo hasta el último elemento, hacer:

• Suponer ordenados los (i-1) primeros elementos.
• Tomar el elemento i.
• Buscar su posición correcta.
• Insertar dicho elemento, obteniendo i elementos ordenados.

Este método se basa en el principio de comparar e intercambiar pares de elementos adyacentes hasta que todos estén ordenados.

Desde el primer elemento hasta el último no ordenado, se debe comparar cada elemento con el siguiente (sucesor) e intercambiar si no están en orden (swaping).

Si tras una pasada puede suceder que ya estén todos los elementos ordenados, en este caso no sería necesario seguir realizando comparaciones.

Si el algoritmo compara primero elementos separados por un amplio intervalo y después se centra progresivamente en intervalos más pequeños, el proceso sería más eficaz. Esto llevo al desarrollo de ordenación Shell y QuickSort.

Su importancia radica en la simplicidad del algoritmo. Una desventaja de este algoritmo es que solo compara los elementos adyacentes del arreglo.

Este método fue desarrollado por el ingeniero civil y matemático Donald Shell, inicialmente hecho para mejorar los ciclos en los motores de los aviones; este fue nombrado como High-speed sorting procedure, aunque se conoce más como Shell Sort, que consiste en la ordenación de subconjuntos de elementos saltando un numero de elementos. Es una versión mejorada del método de inserción directa.

Su algoritmo consite en, primero, ubicar cada elemento en su posición correcta. Para ello, se mueven todos los elementos mayores una posición hacia la derecha. Se selecciona una distancia inicial y se ordenan todos los elementos de acuerdo con ésta. Cada elemento, separado de otro a una distancia, estará ordenado con respecto a dicho elemento. Se disminuye esa distancia progresivamente, hasta que se tenga distancia 1 y todos los elementos estén ordenados.

La complejidad no es fácil de calcular: O(n^3/2), si se divide la distancia a 2,2 tiene una complejidad O(n^5/4); por lo tanto el tiempo de ejecución depende de la secuencia de incrementos que se elige.

El rendimiento de la ordenación Shell es bastante aceptable en la práctica, aún para n grande. Su simplicidad lo hace adecuado para clasificar entradas moderadamente grandes.

Consiste en aprovechar la estructura particular de los montículos (heaps), que son árboles binarios completos (todos sus niveles están llenos salvo a lo sumo el último, que se rellena de izquierda a derecha) y cuyos nodos verifican la propiedad del montículo: todo nodo es mayor o igual que cualquiera de sus hijos. En consecuencia, en la raíz se encuentra siempre el elemento mayor.

Para emplear el método se debe:

• Construir con los elementos a ordenar: un montículo sobre el propio arreglo. Una vez construido el montículo, su elemento mayor se encuentra en la primera posición del vector (a[Primer]).
• Se intercambia entonces con el último (a[Ultimo]) y se repite el proceso para el subvector a[Primero..Ultimo–1]; y así sucesivamente hasta recorrer el vector completo. Esto lleva a un algoritmo de orden de complejidad O(n log n).

Material de apoyo

También conocido como quicksort y desarrollado por C. Antony R. Hoare en 1960. Es un ordenamiento basado en la técnica "divide y vencerás", que permite ordenar n elementos en un tiempo proporcional a n log n.

Originalmente fue desarrollado de forma recursiva pero se utiliza de iterativa para mejorar su rendimiento.

Su funcionamiento consiste en:

• Elegir un elemento de la lista de elementos a ordenar, que se llamará pivote.
• Resituar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada.
• La lista queda separada en dos sublistas, una formada por los elementos a la izquierda del pivote, y otra por los elementos a su derecha.
• Repetir este proceso de forma recursiva para cada sablista mientras éstas contengan más de un elemento. Una vez terminado este proceso todos los elementos estarán ordenados. Como se puede suponer, la eficiencia del algoritmo depende de la posición en la que termine el pivote elegido.
• En el mejor caso, el pivote termina en el centro de la lista, dividiéndola en dos sublistas de igual tamaño. En este caso, el orden de complejidad del algoritmo es O(n•log n).
• En el peor caso, el pivote termina en un extremo de la lista. El orden de complejidad del algoritmo es entonces de 0(n²). El peor caso dependerá de la implementación del algoritmo, aunque habitualmente ocurre en listas que se encuentran ordenadas, o casi ordenadas.
• En el caso promedio, el orden es O(n•log n).

Material de apoyo

Encontrar un elemento específico de un arreglo se denomina búsqueda y en ésta se identifican dos técnicas: la lineal y secuencial.

El objetivo de los algoritmos de ordenamiento permite ejemplificar la importancia del estudio de la eficiencia de los algoritmos y demuestra que no es intuitivo saber cuánto tiempo de ejecución toman y el recurso utilizado para realizar el ordenamiento.

Se seleccionaron los principales algoritmos de ordenamiento y se construyeron a partir de técnicas como selección, inserción, intercambio directo, Shell, montículos y ordenamiento rápido.