Fundamentos

El problema de la ordenación y búsqueda

Fundamentos Nivel medio

Nos alejamos un poco de temas más concretos para introducirnos en el mundo de la ordenación y búsqueda, un problema fundamental en el mundo de la informática que puede llevarnos a resultados sorprendentes sobre temas básicos, recurrentes y, a priori, triviales.

Una pequeña introducción al problema: La guía telefónica

Supongamos que tenemos una de las antiguas guías telefónicas de finales del siglo pasado e inicios del actual. En ellas aparecían, ordenados alfabéticamente, los nombres de todas las personas de un pueblo, ciudad o región con sus números de teléfono (teléfono fijo, por supuesto). Si querías conocer el teléfono de alguien, simplemente ibas a la guía, buscabas su nombre y averiguabas su teléfono.

Pongamos que en esa guía aparecían 100 mil personas. ¿Cómo lográbamos encontrar justamente a la persona que buscábamos? Gracias a que, como hemos comentado, todos los nombres estaban ordenados alfabéticamente, ya fuera por su nombre o por su apellido. Por ello, íbamos directamente a la letra que buscábamos e íbamos acotando hasta llegar a la persona buscada. El proceso podía costarnos, ¿menos de un minuto? En fin, que era un proceso accesible.

La búsqueda al contrario

Ahora imaginemos que, con la misma guía telefónica, lo que tenemos ahora es un número de teléfono y queremos averiguar a quién corresponde. Abrimos la guía teléfonica y, pensamos: ¿ahora qué? ¿Cómo buscar un número de teléfono de entre 100 mil registros que no están ordenados por número? Intentad pensar cuánto tiempo os llevaría leer los 100 mil registros hasta encontrar el que buscáis. ¿Dónde está la clave entonces? En la ordenación y búsqueda.

Ordenación y búsqueda

Gracias a la ordenación y búsqueda, hemos podido encontrar el teléfono buscado en el primer caso muy fácilmente, en segundos, porque teníamos la guía telefónica ordenada por nombre. Sin embargo, en el segundo caso y al tener todos los números desordenados, es posible que nos hubiera costado horas, e incluso días, encontrar la persona propietaria del número.

Imaginemos que el teléfono que nos han dado corresponde casualmente al primero de la lista. En un segundo habríamos encontrado a su propietario y hubiéramos acabado más rápido que si estuvieran ordenados. A esto se le llama el mejor caso. Pero imaginemos ahora que el teléfono es justamente el último de la guía y hemos empezado por el principio. Vamos a tener que leerlos todos hasta llegar al que buscábamos. A este se le llama el peor caso y es aquí, precisamente, donde debemos detenernos. Pese a ello, en muchas ocasiones, lo que buscaremos será el caso promedio, que sería el estadísticamente más probable.

Por este motivo, en el caso de la ordenación y búsqueda, será normalmente el caso promedio el que tendremos en cuenta. Pero, por ejemplo, si estuviéramos controlando una central nuclear y tuviéramos que obtener un resultado lo más rápido posible, analizaríamos el peor caso posible, por muy improbable que sea, no vaya a ser que luego tengamos algún susto.

El coste en el mundo de la algoritmia

De esta forma, tenemos lo que se denomina coste para cuestiones de ordenación y búsqueda. Esta rama que analiza los algoritmos es una de las más importantes en el mundo de la computación. Debemos pensar que contamos con recursos finitos (nuestro propio equipo informático, con su limitada capacidad de procesamiento) y que resolver los problemas con velocidad puede ser incluso un tema de vida o muerte en determinados sistemas informáticos. Por eso mismo, conseguir el mejor algoritmo es fundamental para la ordenación y búsqueda.

Antes de nada, ya vimos en el artículo anterior dedicado a la recursión que, en ocasiones, un algoritmo iterativo era mucho mejor y más rápido que un algoritmo recursivo. Por tanto, en los casos de ordenación y búsqueda esto se incrementa, pues buscar y acceder rápidamente a un elemento puede ser la diferencia entre encontrar una solución o, directamente, quedarnos sin ella.

El coste expresado como orden

En primer lugar, no vamos a entrar ni a desarrollar todo el entramado matemático del cálculo de la complejidad de los algoritmos, pues no es el objetivo de este artículo ni de este blog, ya que es un tema que daría para mucho recorrido. Sin embargo, sí vamos a definir y ver algunos aspectos para saber un poco “de qué va” todo esto.

Se establece, para categorizar a los algoritmos, lo que se llama el orden. Este orden podemos definirlo, dicho mal y pronto, como el número máximo de repeticiones que hará nuestro algoritmo para solucionar el problema. Así pues, podemos tener un orden constante, expresado como O(1), un orden logarítimo O(log n), lineal O(n), casi lineal O(n log n), cuadrático O(n2), cúbico O(n3) o exponencial O(2n). Estas son las formas más comunes de encontrarnos el orden en los algoritmos.

Midiendo los tiempos

Y pensaréis, ¿y todo esto para qué? Imaginemos que tenemos siete algoritmos, todos llegan al mismo resultado, pero cada uno tiene un coste distinto. Y que ese algoritmo, normalmente de ordenación, recibe elementos que tiene que ordenar. A continuación, veamos en una tabla cuánto tiempo (por ejemplo en segundos) le costaría a cada algoritmo completar el proceso:

ElementosO(1)O(log n)O(n)O(n log n)O(n2)O(n3)O(2n)
11111112
21122484
41248166416
81382464512256
16141664256409665536
3215321601024327684294967296
64166438440692621445834601725 ¡siglos!

Años y siglos para resolver problemas

Sí, siglos, con 64 elementos el tiempo de ejecución del algoritmo de orden exponencial se nos va a más de 5000 millones de siglos si contamos que una instrucción le cuesta un segundo realizarla. Leéis bien, siglos. Y sí, miles de millones de siglos. Aunque con 32 elementos ya se nos iba a 136 años. Igualmente, tampoco se queda corto (aunque muy lejos del exponencial) el cúbico, pues con 64 elementos le costaría más de tres días terminar. Ciertamente, las instrucciones se suelen ejecutar en microsegundos, pero ya podemos reducir algunos ceros que igualmente tendríamos siglos.

De ahí la importancia del estudio del coste de los algoritmos, especialmente en la ordenación y búsqueda. Un algoritmo pésimamente realizado o muy especial que cuente con un coste exponencial, puede llevarnos a una operación irresoluble a poco que el problema crezca. Pero no nos quedemos ahí, pues un algoritmo de orden cúbico con sólo ocho elementos ya nos llevaría, si cada instrucción le costara un segundo, a más de ocho minutos de ejecución.

Ordenación

Este tipo de problemas se ponen especialmente de manifiesto en la ordenación de una serie de elementos. Cogiendo de nuevo el ejemplo inicial de la guía de teléfonos, el algoritmo de búsqueda del teléfono, yendo de uno en uno, es lineal, es decir, en el caso peor recorreríamos los 100 mil números de la guía hasta encontrar el que buscamos. Mientras que la búsqueda con un algoritmo ordenado sería del orden logarítmico y reduce muchísimo la búsqueda, pues en unos pocos segundos hemos encontrado a quien buscábamos.

Es por ello que ordenar cosas es tan importancia, para luego encontrarlas de forma más accesible. La ordenación y búsqueda van muchas veces de la mano. Así pues, en este artículo vamos a presentar varios algoritmos de ordenación para ver cómo actúan y cuáles son sus costes. Al final del artículo, veremos qué algoritmo utiliza la función sort() de PHP.

Algunos de los algoritmos que vamos a ver para ordenar se utilizan habitualmente para introducir el tema en los cursos de programación debido a que son fáciles de entender, pero no suelen ser los mejores excepto el último que veremos y que sí es más utilizado. Además, vamos a simplificar el proceso de ordenado considerando que tenemos arrays que contienen números nada más. El proceso se complicaría si tuviéramos otro tipo de datos más complejos.

Algoritmo de ordenación por selección

Ordenación y búsqueda son aspectos fundamentales cuando contamos con muchísimos elementos, así que el primero de los ejemplos va a ser el algoritmo de ordenación por selección. Básicamente consiste en que recorremos una vez todos los elementos y nos quedamos con el menor, el cual colocamos luego en primera posición. Después, volvemos a recorrer todos los elementos restantes y buscamos el nuevo menor para colocarlo en la segunda posición.

Veamos el algoritmo en forma de función y luego lo explicaremos:

FUNCIÓN ordenacionPorSeleccion(array) {
  numElementos = CONTAR ELEMENTOS array
  FOR (i = 0; i < numElementos - 1; i++) {
    minimo = i
    FOR (j = i + 1; j < numElementos; j++) {
      IF (array[minimo] > array[j]) {
        minimo = j
      }
    }
    aux = array[minimo]
    array[minimo] = array[i]
    array[i] = aux
  }
  DEVOLVER array
}

Una pequeña traza

Vamos a probar este algoritmo con una pequeña traza. Para ello, utilizamos un array con los valores 5, 3, 4, 1 y 2, colocados en ese orden. Al iniciarse la función, lo primero que hacemos es calcular el número de elementos, que será de 5. Después:

PasoArrayPosición minimoPosición iPosición jExplicación
15,3,4,1,2null0nullEntramos en el bucle FOR y asignamos a i el valor 0
25,3,4,1,200nullAsignamos el valor de i a minimo
35,3,4,1,2001Entramos en el segundo bucle FOR y asignamos a j el valor de i+1, pues queremos recorrer a partir del siguiente elemento del array
45,3,4,1,2101El elemento de la posición de minimo, es decir, array[0], es un 5 y es mayor al elemento de la posición de j, es decir, array[1]. Por tanto, la nueva posición de minimo es 1
55,3,4,1,2102Avanzamos en el segundo bucle y ahora j cogerá el valor 2
65,3,4,1,2102Como el elemento de la posición de minimo es un 3 y el de la posición de j, que ahora es array[2] es un 4, nada cambia
75,3,4,1,2103j coge el valor 3
85,3,4,1,2303minimo se refería a array[1], pero ahora llegamos a que array[3], que es donde apunta j y que vale 1, es menor, así que el nuevo minimo es 3
95,3,4,1,2304j coge el valor 4
101,3,4,5,2304Como array[3] no es mayor a array[4], entonces minimo no cambia y, al llegar al final, hacemos el intercambio. Con el valor de i cogemos lo que había en array[0], nos lo guardamos y se lo modificamos con el valor de array[3], que es donde indica minimo que está el elemento de menor valor. Luego ponemos en array[3] el valor que nos habíamos guardado de array[0]
1,3,4,5,2112(Vayamos un poco más rápido). Ahora vamos por la segunda iteración del primer bucle, con i cogiendo el valor 1 y minimo también. Para j, ahora empezamos con 2
1,3,4,5,2414Algunas iteraciones después, hemos llegado a que el nuevo valor menor es el de la posición array[4], que es donde apunta minimo y que vemos que contiene un 2
1,2,4,5,3Hacemos el intercambio y colocamos el valor 2 en segunda posición, y el valor que había en esta posición, el 3, en la posición donde estaba el 2
1,2,3,5,4Una iteración del primer bucle después, habremos intercambiado el 4 por el 3
1,2,3,4,5Al llegar al final, intercambiaremos el 5 por el 4 y finalizaremos. La última iteración no se ha hecho (de ahí que hayamos puesto numElementos – 1 en el primer FOR), porque el último número siempre va a estar ordenado

Coste del algoritmo

Como hemos comentado, no nos vamos a parar mucho en cuestiones matemáticas, pero sí decir que el coste de este algoritmo sería la suma de (nº elementos – 1) + (nº elementos – 2) + … + 2 + 1, que es igual a nº elementos multiplicado por nº elementos – 1 y dividido todo por 2. En definitiva, que tendríamos un orden cuadrático O(n2), por lo que podemos pensar sólo viéndolo que el algoritmo sería muy costoso cuantos más elementos tuviera, porque recorrerlos todos una y otra vez, aunque la cantidad sea menor cada vez, conlleva un tiempo.

Algoritmo de ordenación por intercambio

Con este algoritmo veremos uno de los métodos más famosos en cuanto al tema de ordenación y búsqueda, el método de la burbuja. Aunque ineficiente conforme la lista de elementos se va haciendo muy larga (como casi todos, ciertamente), es sencillo de comprender. En esta ocasión lo que vamos a buscar es el intercambio de dos elementos correlativos. Si el segundo elemento de los que estemos observando es menor que el anterior, los intercambiamos. Así llegaremos a una situación en la que el último elemento siempre será el mayor. Por tanto, deberemos volver a realizar lo mismo con todos los elementos excepto el último, y así hasta tenerlos todos ordenados.

El algoritmo, en nuestro pseudocódigo, es el siguiente:

FUNCIÓN metodoBurbuja(array) {
  numElementos = CONTAR ELEMENTOS array
  FOR (i = 1; i < numElementos; i++) {
    FOR (j = 1; j < numElementos - i; j++) {
      IF (array[j] > array[j+1]) {
        aux = array[j+1]
        array[j+1] = array[j]
        array[j] = aux
      }
    }
  }
  DEVOLVER array
}

Una pequeña traza

En primer lugar, vamos a utilizar de nuevo el mismo array con valores 5, 3, 4, 1 y 2 para ver cómo funciona este algoritmo. Por tanto, veremos paso por paso cómo va ordenándose al igual que antes.

PasoArrayPosición iPosición jExplicación
15,3,4,1,21nullEn primer lugar asignamos a i el valor 1. ¿Por qué no desde 0? Porque i se usa como contador de las veces que vamos recorriendo el array y será j desde donde empezaremos y haremos las comprobaciones
25,3,4,1,210El segundo bucle inicia a j con valor 0 y llegará hasta el final del array excepto por la cantidad de veces que ya hayamos ejecutado el primer bucle, expresado por el valor de i, pues esos elementos del final estarán ya ordenados
33,5,4,1,210A la primera ya hemos visto que array[0], indicado por la j, es mayor que array[1], indicado por, atención, j+1, es decir, el siguiente número. Procedemos a su intercambio
43,4,5,1,211De igual forma que en el paso anterior, array[1] tenía un valor mayor a array[2], así que lo intercambiamos
53,4,1,5,212De nuevo, array[2] es mayor que array[3], así que otro intercambio
63,4,1,2,513Y, por último, también array[3] era mayor que array[4], así que realizamos el intercambio de nuevo. Esto ha pasado así porque el 5 era el valor más alto y estaba justo al principio, así que se ha ido moviendo hasta el final del array
73,4,1,2,520Entramos en la segunda iteración del primer bucle, es decir, la segunda vez que recorremos todos los elementos excepto el último, en esta ocasión. En la primera pasada array[0] es menor que array[1], así que todo sigue igual
83,1,4,2,521Sin embargo, ahora array[1] era mayor que array[2], así que lo intercambiamos
93,1,2,4,522Pasa igual en la última iteración de este recorrido para que, al final, el 4 haya llegado a su posición final. Recordemos que en esta pasada no llegábamos hasta el final
101,3,2,4,530Iniciamos el tercer recorrido y vemos que array[0] tiene un 3 y array[1] tiene un 1, así que los intercambiamos
111,2,3,4,531En la siguiente ocurre lo mismo, así que hacemos el intercambio y finalizamos este recorrido al haber llegado al final
121,2,3,4,540Aunque ya lo veamos ordenado, el algoritmo va a seguir. En el siguiente recorrido con los dos últimos elementos, ve que array[0] no es mayor que array[1] y los deja igual. Ahora sí, hemos terminado

Coste del algoritmo

En esta ocasión hablaremos también de un coste cuadrático O(n2) como en el anterior caso. Podríamos mejorar un poco el algoritmo teniendo una variable que, si en algún recorrido no ha intercambiado ningún valor, es que ya está ordenado. Imaginad un array de 100 elementos que resulta que, después de recorrerlo 50 veces, ya está ordenado. El algoritmo que hemos visto seguiría hasta recorrerlo las 99 veces, con el coste que eso supone. Pero con una pequeña variable indicándole que no ha habido intercambios en un recorrido completo, se soluciona. Pese a ello, el coste seguiría siendo cuadrático porque el caso peor es recorrerlos todos.

Algoritmo de ordenación por inserción

Este algoritmo cuenta con la siguiente descripción. En primer lugar, cogemos un subarray de elementos con únicamente un elemento, el cual estará obviamente ordenado. A continuación, miramos el segundo elemento y lo comparamos con el último elemento del array ordenado que ya teníamos (que por ahora tiene un elemento). Si es mayor, lo colocamos detrás y listo. Si es menor, lo comparamos con el siguiente valor más a la izquierda. Como estamos al principio, lo colocamos ahí. Después seguiríamos con el siguiente valor, primero comparándolo con el último y, si es menor, comparándolo con el siguiente más cercano hasta encontrar así su posición. Veamos el algoritmo:

FUNCIÓN ordenamientoPorInsercion(array) {
  numElementos = CONTAR ELEMENTOS array
  FOR (i = 1; i < numElementos; i++) {
    comparador = array[i]
    j = i - 1
    WHILE (j >= 0 && aray[j] > comparador) {
      array[j+1] = array[j]
      j = j - 1
    }
    array[j+1] = comparador
  }
}

Una pequeña traza

Leer el algoritmo puede provocar algún dolor de cabeza, pues es difícil ver qué está haciendo sin una traza. En este caso indicaremos en negrita los elementos ya ordenados. Vamos a verla.

PasoArrayPosición iPosición jComparadorExplicación
15,3,4,1,21nullnullInicialmente recorremos el array desde la posición 1, no desde la 0. Además, el primer valor, el 5, “ya está ordenado”
25,3,4,1,210nullTenemos a j que coge el valor i-1, o sea 0, por eso no hemos iniciado el paso anterior desde 0
35,3,4,1,2103El comparador coge el valor de array[1] que es 3
45,3,4,1,2103La condición del WHILE se cumple, pues j es mayor o igual a 0 y array[0], que es 5, es mayor a comparador
55,5,4,1,21-13Hemos colocado en array[1] el valor de array[0] y restado uno a j. Ahora la condición del WHILE no se cumple y saldrá
63,5,4,1,21-13No, no habíamos perdido el 3, estaba guardado en comparador. Al salir del WHILE lo colocamos en array[0]
3,5,4,1,2214En la segunda iteración, el valor comparador ahora será el 4
3,5,5,1,2204Ocurre lo mismo dentro del WHILE. La primera vez array[1] era mayor que el comparador, así que copiamos el 5. Pero la segunda vez array[0] no es mayor que el comparador, así que ahí sale del bucle
3,4,5,1,2204Recuperamos el 4, que estaba en comparador y lo colocamos en su sitio, en array[1]
1,3,4,5,2Varias instrucciones después, el 1 se hubiera insertado al principio
1,2,3,4,5Y, finalmente, el 2 se hubiera insertado después del 1 y antes del 3. Nuestro array está ordenado

Coste del algoritmo

Si analizamos el coste, de nuevo estamos en el mismo caso que los anteriores. Nos debemos fijar en que todos estos métodos recorrern el array una vez, luego lo recorren de nuevo más pequeño y así hasta llegar a la solución. Estamos, de nuevo, en un O(n2).

Algoritmo de ordenación Quicksort

Llegamos al último algoritmo de ordenación que vamos a ver en nuestro intento de que la ordenación y búsqueda sea un problema menos del que ocuparnos. Después de haber visto algoritmos ineficientes en cuanto a su coste, vamos a ver ahora un famoso algoritmo de ordenación, Quicksort, utilizado por PHP (con alguna pequeña variación) para su función de ordenamiento sort(). También muchos otros lenguajes de programación lo utilizan en sus funciones de ordenación.

Este algoritmo es, en esencia, un algoritmo de intercambio, con lo que podría parecerse al método de la burbuja. Pero utiliza recursividad para mejorar el rendimiento. Veamos primero su pseudocódigo.

FUNCIÓN quicksort(array) {
  arrayIzquierda = []
  arrayDerecha = []
  IF (CONTAR ELEMENTOS array < 2) {
    DEVOLVER array
  }

  indicePivote = ÍNDICE DEL PRIMER ELEMENTO DE array
  pivote = array[0]
  QUITAR PRIMER ELEMENTO DE array
  FOREACH (array AS valor) {
    IF (valor <= pivote) {
      AÑADIR valor A arrayIzquierda
    } ELSE {
      AÑADIR valor A arrayDerecha
    }
  }
  arrayPivote = [indicePivote => pivote]
  arrayOrdenado = JUNTAR quicksort(arrayIzquierda), arrayPivote, quicksort(arrayDerecha)

  DEVOLVER arrayOrdenado
}

Una pequeña traza

Este algoritmo utiliza la recursividad para aplicar el diseño de una estrategia denominada divide y vencerás. Es una estrategia avanzada que espero podamos ver algún día, pero no es objeto del actual artículo. Básicamente, intenta dividir un problema mayor en problemas más pequeños hasta alcanzar un problema con una solución evidente. Por ello utiliza recursividad.

El algoritmo coge un valor como pivote y va viendo “dónde” encaja dependiendo de los valores que se va encontrando. Una vez encuentra un lugar, divide el problema en dos subproblemas con arrays cada vez más pequeños. El array de la izquierda tendrá siempre valores más pequeños al del pivote, mientras que el de la derecha los tendrá siempre mayores. Por lo tanto, el pivote ya estará ordenado. En último lugar, va juntando los arrays troceados conforme van siendo ordenados. Vamos a ver la traza un poco distinta a las anteriores.

5,3,4,1,2
Nuestro array inicial desordenado
3,4,1,2 | 5 | array vacío
Como 5 es el número mayor y es el que ha sido escogido como pivote, va buscando su sitio hasta llegar al final, por lo que el array de la izquierda será 3,4,1,2 y el de la derecha será un array vacío, luego acabaría siendo descartado
1,2 | 3 | 4 | 5
Ya hemos quedado que, por el lado derecho, no había nada. Por el izquierdo tenemos un array de cuatro elementos del cual se coge el 3 como pivote. Esto genera un nuevo array a izquierdas con el 1 y el 2, mientras que a derechas se crea un array con el 4 nada más. Nuestro pivote ya está en su sitio
1 | 2 | 3 | 4 | 5
El array con el 1 y el 2 coge como pivote el 1 y sólo genera ahora un array a la derecha con el 2. Mientras tanto, el array a la derecha que sólo tenía el 4 llega al caso base, ya está ordenado
1,2 | 3 | 4 | 5
A continuación empezamos a juntar ahora los arrays ya ordenados por su cuenta
1,2,3,4 | 5
Seguimos dando pasos atrás y juntando el array
1,2,3,4,5
Finalmente, hemos llegado al array final completamente ordenado

Coste del algoritmo

Sólo hay que ver lo que nos ha costado realizar las trazas de los algoritmos anteriores, que en algunas ocasiones hemos omitido cosas, para ver que ahora todo se ha ordenado más rápidamente. Debido a esto, tenemos que pensar que el coste debe ser mejor. Más bien no, pues el coste de este algoritmo es O(n2) también. ¿Cómo es entonces que ha sido más rápido?

Recordad que el coste se expresa en el caso peor, especialmente para situaciones críticas, pero en la mayoría de los casos un buen caso promedio es suficiente. Por suerte, el algoritmo Quicksort en particular tiene un caso promedio de O(n log n), por lo que su rendimiento es muy bueno y suficiente para la mayoría de situaciones sin necesidad de consumir muchos recursos. El caso peor, si no estoy equivocado ahora, sería el de encontrarse un array completamente al revés, es decir, ordenado de mayor a menor. Ahí el pivote siempre tendría que llegar hasta el final en todos los pasos. Es un buen algoritmo para ordenación y búsqueda.

Otros algoritmos de ordenación

En conclusión, hay un buen puñado más de algoritmos de ordenación que nos facilitarán luego la ordenación y búsqueda en nuestros programas. Ordenamiento con árbol binario, ordenamiento Shell, ordenamiento por montículos o uno también muy conocido, el ordenamiento por mezcla o Mergesort. Además, este último también aplica la estrategia de divide y vencerás, pero nos lo dejaremos para cuando llegue ese momento de explicar dicha estrategia.

Esperamos que, al menos, hayamos visto que un buen algoritmo puede salvar vidas o tenernos eternamente esperando a su resolución.

Finalizado este artículo y el de la recursividad, estamos listos para un nuevo reto en A practicar… que puede ponernos las cosas un poco más difíciles después de lo que hemos visto.

Deja una respuesta