Comenzamos entonces con los ordenamientos, el primer tema del curso. Si se ha tomado antes un curso sobre estructuras de datos entonces le sera familiar el tema. Aquí se dará un vistazo los algoritmos ya existentes que se han inventado para la ordenación de elementos, aquí hay algunos videos del canal Chio Code que explican estos algoritmos de una manera simplificada para mayor comprensión:
QuickSort: Este es un algoritmo de ordenamientos clásico que parte de la estrategia divide y vencerás, la idea del algoritmo es elegir un pivote en nuestro arreglo de elementos a ordenar una vez seleccionado entonces tendremos 2 sub arreglos de elementos, los que sean mayores que el pivote y los que sean menores que el pivote, la idea es aplicar el algoritmo anterior recursiva mente sobre los sub arreglos de elementos que vallamos formando para eventualmente lograr ordenar nuestros elementos, el punto malo es que la selección de nuestro pivote es importante para la complejidad del algoritmo puesto que si se elije un mal pivote, uno en el que por ejemplo todos los elementos son mayores o menores que el pivote entonces esto puede disparar nuestra complejidad hasta volverla cuadrática en el peor caso. A continuación se deja un video de apoyo para una mayor comprensión del algoritmo:
MergeSort: También basado en la estrategia de divide y vencerás la idea de este algoritmo es dividir nuestro conjunto de elementos en mitades hasta que se llegue al subconjunto mas pequeño que contiene solo un elemento una vez hecho esto comparamos los sub arreglos para combinarlos en un nuevo sub arreglo que ya esta ordenado, hacemos lo mismo para los sub arreglos restantes hasta que eventualmente nos quede un nuevo arreglo que estará completamente ordenado, como dividimos nuestro arreglo original y luego lo combinamos para formar los sub arreglos ordenados la cantidad de veces que lo fuimos dividiendo siempre entonces este algoritmo tiene una complejidad O(nlogn) siempre, la cual es la máxima a la hora de ordenar con elementos que no conocemos. A continuación se deja un video de apoyo para una mayor comprensión del algoritmo:
InsertionSort: Este algoritmo de ordenamientos es el mas intuitivo de todos dado un arreglo que queremos ordenar seleccionamos nuestro elemento a ordenar como pivote y lo comparamos con el resto de elementos para determinar la posición a la que pertenece, esto mismo lo haremos con el resto de elementos en el arreglo, al final del algoritmo tendremos entonces las posiciones correspondientes a cada elemento en nuestro arreglo y estará ordenado, lo malo es que no es muy eficiente puesto que al seleccionar uno y comparalo con el resto, para cada elemento que tenemos en el arreglo dará una complejidad cuadrática para el algoritmo por lo que seria ineficiente para arreglos que tengan un tamaño muy grande. A continuación se deja un video de apoyo para una mayor comprensión del algoritmo:
Aunque la cota máxima para ordenar elementos que no conocemos es O(nlogn) hasta la fecha si dichos elementos son números entonces existen algoritmos que pueden ordenar mas eficientemente ya que no usan comparaciones, se auxilian mas bien de rangos que ya tengan cierto orden para usarlos como guiá y poder con ellos determinar la posición de nuestros números, estos son los algoritmos de counting sort y radix sort, A continuación dejamos dos videos del canal ChioCode en los que se explican a detalle dichos algoritmos:
Counting Sort:
RadixSort:
Podemos ademas, ordenar nuestros elementos haciendo uso de arboles binarios, auxiliandonos de estructuras de datos que ya hemos visto anteriormente como lo son los arboles de torneo, los montículos mínimos(min-heaps) y montículos máximos (max-heaps), un algoritmo popular que hace uso de lo antes mencionado es el llamado heap-sort, este consta de interpretar nuestro arreglo como un arbol binario y hacer uso de un max-heap, para poder ordenar los elementos en nuestro arreglo nos fijamos en la raíz que sera el elemento mas grande en nuestro arreglo y lo intercambiamos con el ultimo elemento del arreglo, dicho elemento sera una hoja del max-heap, procedemos a eliminar esa hoja, así tenemos ordenada nuestra ultima entrada en el arreglo, consideramos nuestro arreglo desde la primer hasta la entrada n-2 (pues la ultima ya esta ordenada) como otro árbol binario y auxiliandonos nuevamente de un max-heap repetimos el proceso anterior, esto lo hacemos hasta que nos quede solo la raíz y por tanto nuestro arreglo estará ordenado totalmente. Para una mejor ilustración del funcionamiento y complejidad del algoritmo tendremos el siguiente video de apoyo de la mano del canal Michael Sambol (el video esta en ingles pero se pueden activar subtítulos en español por si resulta difícil de entender):
Ya vimos como ordenar cosas, pero también hay que ver como podemos buscar cosas, los dos algoritmos mas populares serian búsqueda lineal y búsqueda binaria, la búsqueda lineal sigue el simple principio de dado el elemento que se desea buscar recorrer todo el arreglo donde queremos buscar y eventualmente encontrar nuestro elemento si se encuentra, si acabamos de recorrer nuestro arreglo sin coincidencias de dicho elemento significara que no estaba en el arreglo, la otra forma es búsqueda binaria la cual resulta mas eficiente puesto que vamos restringiendo los rangos de búsqueda en el arreglo, primeramente ordenamos nuestro arreglo, una vez ordenado nos posicionamos a la mitad de este y observamos si de casualidad ese es el elemento buscado si lo es lo encontramos, si no lo es entonces observamos que relación tiene nuestro elemento buscado con el elemento de la mitad del arreglo, si es menor entonces aplicamos el algoritmo en el sub arreglo desde la posición anterior a nuestro pivote en el arreglo hasta el inicio del arreglo, si es mayor entonces aplicamos el algoritmo en el sub arreglo desde la posición siguiente a nuestro pivote en el arreglo hasta el final del arreglo, hacemos este procedimiento recursivamente hasta encontrar nuestro elemento buscado. A continuación dejamos dos videos referentes a dichos algoritmos para una mejor compresión:
Búsqueda binaria, de la mano del canal de youtube Coding Tree:
Busqueda lineal, de la mano del canal de youtube Programa Tutos:
Usando la idea de Quick-sort podemos encontrar otro algoritmo eficiente para buscar el k-esimo elemento mínimo el cual se conoce como Quick-selection, supongamos un arreglo de tamaño n, en el algoritmo elegimos un pivote que similarmente a quick-sort ordene a la izquierda los elementos menores y a la derecha los elementos mayores a nuestro pivote, si el pivote y nuestro indice en el arreglo k-1 (puesto que el arreglo va de 0 a n-1) son iguales, significa que hallamos nuestro k-esimo elemento deseado, de lo contrario similarmente a búsqueda binaria comparamos la relacion entre nuestro indice k-1 buscado con el indice de nuestro pivote si es mayor a nuestro k-1 buscado entonces buscaremos en el sub arreglo desde 0 hasta el indice anterior de nuestro pivote y aplicamos el algoritmo en ese sub arreglo, de lo contrario entonces el rango del sub arreglo sera desde el indice siguiente de nuestro pivote hasta el indice n-1 del arreglo y aplicamos el algoritmo en este sub arreglo, hacemos este procedimiento recursiva mente hasta encontrar nuestro k-esimo elemento. Este algoritmo tiene un tiempo promedio O(n) (lineal) en el mejor caso, pero como esta basado fuertemente en Quick-sort la selección del pivote afecta la complejidad del misma puesto que si nos tocan varios pivotes malos seguidos en los que descartemos solo un elemento como en Quick-sort la complejidad se dispara a cuadrático. A continuación dejamos un video para una mayor comprensión del algoritmo de la mano del canal de youtube CS Robot (el video igualmente esta en ingles pero se pueden activar subtitulos en español por si se tiene dificultad al comprender):
Hemos visto que en algoritmos que se selecciona un pivote aleatorio existe la posibilidad de que si se selecciona mal nuestra complejidad sufra bastante, por ello también veremos como poder buscar un buen pivote para, con la ayuda de este algoritmo poder tener siempre una buena complejidad en dichos algoritmos mencionados anteriormente, vamos entonces a encontrar la mediana de medianas, para este algoritmo suponga que tenemos una lista de n elementos, vamos a dividir dicha lista en particiones de 5, si la lista no tiene longitud de algún múltiplo de 5 quiere decir que en una sub-lista nos quedaran menos de 5 elementos pero no hay ningún problema con ello, ahora ordenamos las sub-listas que al estar restringidas por elementos de a lo mas 5 siempre entonces ordenarlos sera lineal, una vez hecho esto podemos posicionarnos a la mitad de cada lista y esa sera su mediana, en otra lista digamos M almacenamos las medinas de cada sub-lista creada, ordenamos la lista M y seleccionamos la mitad, el elemento en la mitad sera entonces nuestra mediana de medianas buscada todo esto en tiempo lineal, esto puede aplicarse a algoritmos que dependan de un buen pivote como Quick-sort o Quick-selection para mejorar su complejidad significativamente. A continuación dejamos un articulo que explica a detalle el algoritmo (el material esta en ingles por lo que se recomienda traducir el texto en algún traductor online por si no es clara alguna parte.):
Algoritmo para hallar la mediana de medianas de la mano de Brilliant: Median-of-medians Algorithm.
