Lección 31: Métodos de búsqueda y ordenación

[Vlady_18]

Métodos de Búsqueda y Ordenación:


En la primera parte del curso, donde hablábamos de Pascal, no hice casi énfasis en utilizar ciertos algoritmos para la resolución de problemas ya que mi foco estaba en que aprendieran un lenguaje y a utilizar este para resolver problemas de la mejor manera que ustedes pudieran. Claro está que los ejemplos y los ejercicios siempre han sido pensados para forzarlos a ustedes a razonar de cierto modo y así llevarlos implícitamente a utilizar buenas prácticas de programación, sobretodo los proyectos, que eran los problemas más complejos que debían resolver, teniendo en cuenta que en los proyectos finales sí se les pedía utilizar tal o cual algoritmo para resolver un problema específico. Sin embargo yo quería que en ese curso tuvieran un primer choque con la programación, desde la nada, desde el “Yo no tengo ni idea de qué es programar” y lograr así que rompieran con una barrera muy fuerte.


De este modo, ahora ya no me centraré en que aprendan a programar, que aprendan a pensar de forma lógica y estructurada, sino que pondré el foco en enseñarles nuevas técnicas de programación las cuales sirven para resolver problemas complejos y sin las cuales no podrán hacer mucho más de lo que ya han hecho. Por ejemplo, como ya he nombrado mil veces, dividir el programa en módulos individuales para utilizarlos todos desde un módulo principal, pero aún falta para eso.


Lo que presentaré ahora había sido pensado en realidad para ser mostrado en el primer curso, pero a mi juicio sería demasiado. Es así que he decidido hacerlo ahora. Luego de presentar este tema les dejaré un montón de ejercicios de aplicación para que se pongan bien a tiro con Modula, dejándoles algunas soluciones seleccionadas sobre los ejercicios más complejos.
-------------------------------------------------------------------------------------


Búsqueda:


Presentaré primero dos métodos de búsqueda de un elemento en un arreglo. Ustedes podrían extender estos métodos a alguna otra estructura, pero su mejor aplicación es para arreglos. Más que métodos son algoritmos, algoritmos bien conocidos en el mundo de la programación.


Seguramente, si yo les digo que creen un arreglo de enteros de 100 celdas y lo rellenen con números, y luego les pido que busquen si un número está dentro del arreglo, ustedes podrán hacerlo bien, o sea, sabrán encontrar el número si está o decirme que no está si no lo encuentran ahí.


Sin embargo, el hecho de que algo esté bien hecho no significa que esté hecho de la mejor manera, o sea, de la manera más eficiente. En este curso insistiré un poco con la eficiencia de los programas y les enseñaré algunos algoritmos muy buenos para algunos casos introduciéndolos muy levemente al Análisis de Algoritmos, pero solo muy levemente ya que eso en realidad corresponde a toda una rama de la computación y pues contiene matemática muy pesada, yo mismo no he querido meterme mucho en esa rama. Entonces les daré conceptos básicos para que sepan medir algunas cosas, pero nada más. Si alguno quisiera aprender conceptos avanzados sobre el análisis de algoritmos pídamelo explícitamente y se los explicaré, pero no es el punto de este curso en absoluto, así que no se preocupen. La idea siempre es que puedan salir adelante solo y únicamente con lo que yo les doy aquí sin que tengan que salir a buscar nada en ninguna parte.


-----------------------------------------------------------------------------------


Búsqueda Lineal:


Dado un arreglo que contenga algún tipo de elementos, y un elemento de ese tipo, buscar linealmente dicho elemento en el arreglo no es más que comenzar desde el principio e ir mirando secuencialmente cada celda del arreglo hasta encontrar el elemento buscado. En el peor de los casos recorreríamos todo el arreglo hasta el final sin encontrar el elemento o encontrando este justo al final del arreglo.
Supongan que tenemos un arreglo de enteros de 100 elementos tal como se declara aquí:

CONST
	MAX_LARGO_ARREGLO= 100;
TYPE
	arreglo: ARRAY[1..MAX_LARGO_ARREGLO] OF INTEGER;

Ahora supongan que tenemos una función BuscarEelemento que recibe un arreglo y un elemento a buscar como parámetros, retornando la posición del elemento en el arreglo si lo encuentra, o -1 en caso contrario. Esta función utilizará la búsqueda lineal:

PROCEDURE BuscarElemento(arr: ARRAY OF INTEGER; elem: INTEGER): INTEGER;
VAR
	i: INTEGER;
BEGIN
	i:= 1;
	WHILE (i<= MAX_LARGO_ARREGLO) AND (arr[i]<>elem) DO
		i:= i + 1;
	END;
	
	IF i<= MAX_LARGO_ARREGLO THEN
		RETURN i;
	ELSE
		RETURN -1;
	END;
END BuscarElemento;

Veamos esto, no es nada complejo pero lo describiré para que quede bien claro.


Nos declaramos una variable entera i que será la iteradora, o sea, la que usaremos para ir mirando las celdas del arreglo. Luego inicializamos esta variable en 1 ya que sabemos como está declarado el arreglo, de otro modo deberíamos inicilizarla con otro valor, o sea, siempre con el primer valor del índice del arreglo.


Luego tenemos un WHILE simple con una condición AND, que lo único que hace es aumentar el valor de i en 1 siempre que no hayamos encontrado el elemento y que además i sea menor o igual que MAX_LARGO_ARREGLO. O sea, si no hemos llegado al final del arreglo y a su vez no hemos encontrado el elemento buscado, aumentamos una posición para verificar la en la próxima iteración, en caso contrario nos quedamos con la posición actual ya que encontramos el elemento.


Entonces hay dos posibilidades para salir del WHILE, o bien encontramos el elemento o bien llegamos al final del arreglo sin encontrar nada. Si no encontramos el elemento, llegaría un momento en que i sería igual que MAX_LARGO_ARREGLO (en este caso 100). Entonces, cuando el WHILE verificara su encabezado vería que se cumple i<= MAX_LARGO_ARREGLO y también que arr[i]<>elem, con lo cual aumentaría i en 1. De este modo ahora i sería mayor que MAX_LARGO_ARREGLO, entonces al volver al encabezado del WHILE no se cumpliría la primera condición con lo cual saldríamos del WHILE.


Entonces el IF que está luego del WHILE se encarga de ver por qué salimos del WHILE fijándose en el valor de i. Si esta es menor o igual que MAX_LARGO_ARREGLO implica que salimos porque encontramos el elemento y entonces retornamos el valor de i (la posición del elemento). Si i es mayor que MAX_LARGO_ARREGLO significa que no encontramos nada, entonces retornamos -1.


Hay que notar que el WHILE funciona porque sus condiciones implementan el circuito corto, o sea, si la primera condición del AND es falsa, ya no se verifica la segunda porque sin importar su valor el AND será falso. Si fuera por circuito largo (circuito completo), o sea, si siempre se verificaran ambas condiciones, en el caso en que el elemento no estuviera dentro del arreglo tendríamos un error en tiempo de ejecución ya que llegaría un punto en que i sería mayor que MAX_LARGO_ARREGLO, entonces cuando el encabezado del WHILE verificara i<=MAX_LARGO_ARREGLO esto sería falso, pero igualmente iría a verificar arr[i]<>elem, pero como no existe posición i en el arreglo el programa caería.


Esto no nos preocupa porque sabemos que Modula utiliza circuito corto al igual que Pascal, pero si esto no fuera así entonces tendríamos que pensar en otra manera de verificar si el elemento está o no está en el arreglo.


Les dejo una pequeña ilustración en la cual tenemos un arreglo llamado A, con n cantidad de celdas, donde sus elementos son llamados v1, v2 … vn; y nosotros buscamos al elemento v3.





Como ya dije, usando el método de Búsqueda Lineal, en el peor caso recorremos todo el arreglo, siendo el mejor caso aquel en que el elemento esté en la primera celda. De este modo, si el arreglo es de 1000 elementos tenemos como peor caso 1000 consultas, o sea, preguntamos 1000 veces si el elemento que buscamos es igual al que está en la celda en cuestión. Si bien este método es efectivo, no es muy eficiente. Imaginen una nómina de 20000 personas donde debemos encontrar una. En el peor caso tenemos 20000 consultas en nuestro programa, lo cual es muchísimo, y si miramos un caso intermedio, o sea que la persona que buscamos esté en la mitad del arreglo entonces debemos consultar 10000 veces.


Para nuestros análisis de algoritmos siempre tomaremos en cuenta el peor caso posible. Para este ejemplo tenemos dos peores casos: o bien el elemento está en el último lugar o bien no está en el arreglo, cualquiera de los dos nos llevaría a recorrerlo todo.


De este modo, si tenemos un arreglo de n cantidad de elementos, en el peor caso tendríamos n cantidad de consultas, con lo cual diríamos que nuestro algoritmo de búsqueda es de Orden n. El orden de un algoritmo para nosotros será un número que indica la cantidad de consultas que deben rearlizarse en base al total de elementos, siempre refiriéndonos al peor caso posible.


Existen otras maneras de ver el orden de un algoritmo, por ejemplo, en base a casos intermedios, pero eso no es competente a los efectos de este curso porque no es aplicable.


Como dije, el orden del algoritmo de Búsqueda Lineal es n siendo n el número máximo de elementos. La notación para decir que un algoritmo tiene Orden n es O(n).


-----------------------------------------------------------------------------------


Búsqueda Binaria:


¿Se les ocurre otra forma de buscar un elemento más rápidamente, o sea, que en el peor de los casos no tuviéramos que hacer n consultas?


Aquí les presentaré un método que acelera muchísimo la búsqueda de un elemento, tanto así que si tenemos un arreglo de n cantidad de elementos su orden es log2(n) (logaritmo en base 2 de n). ¿Qué significa esto? Si por ejemplo, tenemos un arreglo de 1000000 (un millón) de elementos, su orden es log2(1000000), lo cual equivale a 20. Sí, para un arreglo de UN MILLÓN de elementos haremos como máximo 20 consultas. Si fueran 100 elementos, como en el caso anterior, tendríamos unas 6 consultas como máximo.


Ahora bien, este algoritmo tiene una contra, y esta es que el arreglo en el que vamos a buscar debe estar ordenado, sea de menor a mayor o viceversa. Si inicialmente el arreglo estuviera desordenado, la tarea de ordenarlo sería tan costosa que es mejor utilizar la Búsqueda Lineal, pero si está ordenado, entonces claramente es mejor usar la Búsqueda Binaria. Por esto es mejor mantener ordenado el arreglo a medida que se insertan elementos en él.


Igualmente, si a futuro fueran a realizarse muchas consultas sobre el arreglo, entonces sí convendría ordenarlo.


El método de Búsqueda Binaria también se conoce como Búsqueda por Bipartición. Funciona de la siguiente manera:


Partimos de la base de que el arreglo está ordenado, entonces miramos si el elemento buscado está a la mitad del arreglo. De este modo partimos en dos al arreglo original.


Si el elemento está a la mitad todo bien, pero si no es así, entonces nos fijamos si el el elemento a buscar es mayor o es menor que el contenido de la celda. Si es mayor entonces ahora buscaremos en la mitad derecha del arreglo original, si es menor buscamos en la mitad izquierda. Por esto el arreglo debe estar ordenado.


Así hemos reducido a la mitad el rango de búsqueda. Supongamos que el elemento que buscamos es mayor que el que está a mitad del arreglo. Entonces ahora debemos buscar en la mitad derecha. Lo que hacemos es tomar esa mitad como un nuevo arreglo y aplicar el mismo método, o sea, buscamos en el medio y vemos si el elemento que está allí es igual al que buscamos. Si no es así entonces vemos si lo que buscamos es menor o mayor que lo que está allí y obtenemos un nuevo rango de búsqueda.
Veamos un ejemplo sencillo en el que tenemos un arreglo de 20 números, como este:





Supongamos que queremos buscar número 38 dentro dele arreglo. Entonces lo que hacemos es ir a la mitad del arreglo y ver si el 38 está ahí. Lo que está en la mitad es el 29 y no el 38. Entonces como 38 es mayor que 29 ahora buscamos en la mitad derecha del arreglo, o sea esta:





Como ven, hemos reducido a la mitad la cantidad de elementos que teníamos inicialmente. Repetimos el método y vamos a la mitad de nuestro arreglo, o sea, a donde está el 34. Nosotros estamos buscando el 38, por tanto como no es el elemento que buscamos vemos si es mayor o menor que lo que encontramos. Nuevamente 38 es mayor que lo que encontramos, entonces vamos a la mitad derecha de nuestro rango, o sea esta:





Nuevamente hemos reducido a la mitad la cantidad de elementos. Vamos entonces a la mitad nuevamente y nos encontramos con el número 37. No es lo que buscamos, entonces vemos que 38 nuevamente es mayor, por tanto nos vamos a la mitad derecha:





Bien, vamos a la mitad de este arreglo. Como tiene dos elementos, la mitad es 1, entonces vamos al 38. Justamente lo encontramos.
Si hubieramos estado buscando el 39 entonces en la próxima consulta solo tendríamos un número para comparar. Lo mismo si estuviéramos buscando, por ejemplo, el 48, que no está en el arreglo.
Entonces, para un arreglo de 20 elementos tenemos un máximo 5 consultas a realizar.
Les dejo otra ilustración de cómo se partiría un arreglo en la búsqueda, coloreando las mitades seleccionadas en cada caso:





Entonces vamos a lo que importa, cómo implementamos esto en Modula. Al igual que en la Búsqueda Lineal, nuestra función BuscarElemento recibe un arreglo y un elemento a buscar, devolviendo la posición en que está el elemento o -1 en caso de que lo que buscamos no esté:

PROCEDRUE BuscarElemento(arr: ARRAY OF CHAR; elem: INTEGER): INTEGER;
VAR
	inf, sup, medio: CARDINAL;
BEGIN
	inf:= 1;
	sup:= MAX_LARGO_ARREGLO;
	medio:= (inf + sup) DIV 2;
	WHILE (inf<=sup) AND (arr[medio]<>elem) DO
		IF elem 

Este algoritmo es un poco más complejo que el anterior, por lo tanto lo describiré más detalladamente.


Lo primero que tenemos es la declaración de las tres variables enteras que usaremos, una será para recorrer el arreglo y las otras dos para discriminar hacia qué lado debemos dirigirnos en caso de no haber encontrado el elemento.


Inicializamos inf en 1 asumiendo que esa es la primera posición del arreglo, sup en MAX_LARGO_ARREGLO sabiendo que más de esa cantidad de celdas no habrá, y luego inicializamos a medio con el resultado de (inf + sup) DIV 2, o sea, con el punto medio del arreglo.


Para nuestro ejemplo de búsqueda del 38 tendríamos:

• inf=1
• sup= 20;
• medio= (1 + 20) DIV 2 = 21 DIV 2 = 10

Deben darse cuenta de inf pretende ser siempre el inicio del arreglo en el que buscaremos y sup siempre el final de dicho arreglo. De este modo las iremos modificando para obtener nuestros rango de búsqueda correctamente. Inicialmente estamos buscando entre la posición 1 y 20 del arreglo, e iremos a verificar en la posición 10 del mismo.


Luego tenemos un WHILE que en su encabezado verifica que nuestra variable inf sea menor o igual que sup y que el elemento en la posición media del arreglo no sea el que buscamos. Si se cumplen ambas cosas, entonces pasamos a este IF:

IF elem 

Si el elemento buscado es menor que lo que hay en la posición media del arreglo entonces ahora nuestra variable sup será la posición media menos un lugar quedando inf como está, y en caso contrario nuestra variable inf será la posición media más un lugar quedando sup como está..


En nuestro ejemplo el elemento buscado era 38 y lo que había en la posición media era un 29, por tanto pasamos a la parte ELSE del IF, donde hacemos inf:= medio + 1. Siguiendo el ejemplo tenemos:

• inf= medio + 1= 10 + 1= 11
• sup= 20
• medio= 10

Luego de ese IF, tenemos una última asignación antes de llegar al END del WHILE:

medio:= (inf + sup) DIV 2;

Con lo cual tendríamos entonces:

• inf= 11
• sup= 20
• medio= (11 + 20) DIV 2= 31 DIV 2= 16

Con esto ahora estamos buscando entre la posición 11 y 20, e iremos a mirar la posición 16 para repetir el procedimiento. Sigan la ejecución de este algoritmo hasta el final de nuestro ejemplo y verán que funciona. También prueben ustedes otros casos, como por ejemplo, buscar un número que no está, tanto porque es mayor que todos como porque es menor, o sea, prueben para ambos lados, y verán que siempre funciona.


NOTA IMPORTANTE: Para el algoritmo de Búsqueda Lineal no se utiliza un concepto de mayor que o menor que, o sea, no hay un concepto de orden ya que la búsqueda se hace secuencialmente hasta hallar el valor indicado o fallar al no encontrarlo. Sin embargo, como han podido ver, para la Búsqueda por Bipartición sí hay un concepto de orden dado que este algoritmo necesita explícitamente que el arreglo esté ordenado.


Ahora bien, resulta sencillo hablar de orden cuando se trata de números ¿pero si nuestro arreglo no es de números? Si por ejemplo es un arreglo de registros ¿cómo se puede ordenar eso? ¿Cómo decimos que un objeto es mayor que otro?


Imaginen estas declaraciones:

TYPE
	TPersona= RECORD
		Nombre, Apellido: ARRAY[1..20] OF CHAR;
		Edad: INTEGER;
	END;
	
	TListaPersonas= ARRAY[1..1000] OF Tpersona;

Allí simplemente tenemos declarado un tipo registro llamado TPersona, el cual contiene el Nombre, el Apellido y la Edad de una persona. Luego tenemos un arreglo cuyas celdas son del tipo TPersona y por tanto cada una es un registro.


Si tuviéramos que buscar una persona en ese arreglo ¿cómo haríamos?
El arreglo podría, por ejemplo, estar ordenado alfabéticamente según el nombre de las personas, por lo tanto, en cada consulta deberíamos fijarnos en ese campo y ver si el nombre que tenemos es mayor, igual o menor que el está en el arreglo. Eso no sería problema utilizando la función Compare de la librería Strings.


Supongan entonces que queremos saber si en la lista está un hombre llamado Pepe. Comenzamos a buscar y resulta que lo encontramos ¿cómo sabemos si ese Pepe es el que buscamos? ¿Y si había más hombres llamados Pepe?


Entonces tendríamos que, una vez encontrada una persona con ese nombre, verificar algo más, por ejemplo, el apellido. Entonces no deberíamos estar buscando solo a alguien llamado Pepe, sino llamado Pepe Algo, por ejemplo Pepe Rodríguez.


El arreglo sigue estando ordenado según el nombre, por tanto buscamos en base a ese campo a alguien llamado Pepe, al encontrarlo verificamos que su apellido sea el mismo que tenemos nosotros.


Imaginen que encontramos a un Pepe Rodríguez, tendríamos el mismo problema, puede haber más Pepe Rodríguez en la lista ¿cómo sabemos si el que encontramos es el que estamos buscando? ¿Verificamos también la edad? No, porque tendríamos el mismo problema. Si por ejemplo buscamos un Pepe Rodríguez de 40 años y resulta que encontramos uno, podría haber más Pepe Rodríguez de 40 años en la lista.


El hecho de ir buscando y comparando varios campos, además de no ser seguro, complica el código y el algoritmo de búsqueda, es por esto que lo que se hace es asignar algo a los elementos que sea único para cada uno. En el caso de las personas, sería bueno por ejemplo, guardar además de su Nombre, Apellido y Edad, el Documento de Identidad.


De este modo podríamos tener el arreglo ordenado según el Documento de Identidad y buscar por ese campo, entonces si lo encontramos sabemos que esa es la persona que buscamos y que no hay otra igual, y si no, es que no está ahí.


Esto es lo que se hace en realidad a la hora de tener grandes registros de información, se denomina un campo que tendrá un valor único para cada elemento. En las personas es el Documento de Identidad, en los productos de supermercado es su Código de Barras, en las empresas es su Número de RUT, etc.


A estos campos únicos se los denomina Clave del objeto. Este es un concepto que se arrastrará luego a las bases de datos y demás. Tal vez algunos de ustedes ya estén familiarizados con esto.


----------------------------------------------------------------------------------


Ordenación:


Siguiendo la línea de la nota anterior, hablaremos entonces de ordenación, o sea, cómo ordenar un conjunto de datos en una secuencia de acuerdo a un criterio especificado. Obviamente para hablar de ordenar hay que hablar de qué criterio se utilizará para dar un orden a los elementos. En nuestros ejemplos vimos que eran números ordenados de forma ascendente, pero bien podría haber sido en forma descendente, o según su cantidad de divisores, u ordenando primero los pares y luego los impares, etc.


El criterio a utilizar se definirá en función de las necesidades del sistema que se esté implementando. Si estamos trabajando con un programa que todo el tiempo utiliza la cantidad de divisores de un conjunto de números porque ese es un dato clave, entonces podría servir ordenar los números según su cantidad de divisores. Claro está que eso no es un valor único para todos los números, pero tal vez no haga falta tener eso en nuestro sistema.


También es posible aplicar más de un criterio a la vez, por ejemplo, ordenar los números de forma ascendente y según su cantidad de divisores. Un criterio como ese habría que definirlo muy bien y muy claramente. Por ejemplo, si tenemos al número 10, este tiene 4 divisores: él mismo, el 5, el 2 y el 1; luego tenemos el 8 que también tiene 4 divisores: él mismo, el 4, el 2 y el 1; y luego tenemos el 23, que tiene dos divisores: él mismo y el 1.


¿Cómo los ordenamos?


¿Estaría bien así?: 8, 10, 23.


¿O así?: 23, 8, 10.


Y pues, no se sabe, depende del criterio. En la primera forma tiene prioridad el valor del número en sí, pero en la segunda forma tiene prioridad la cantidad de divisores y luego el valor del número. Entonces siempre hay que tener los criterios bien claros.


NOTA: Si no lo recuerdan, decimos que un número B es divisor de un número A si A MOD B= 0.
-----------------------------------------------------------------------------------


Ordenación por Inserción:


Este es el primero de leos dos métodos de ordenación que mostraré aquí. El algoritmo es el siguiente:


Dado un arreglo eventualmente desordenado, iremos haciendo recorridas parciales ordenando poco a poco, o sea, asegurando que la porción ya recorrida del arreglo quedó ordenada. Para esto, miramos el arreglo desde el principio pero por trozos que se agrandarán en cada recorrida.
Inicialmente miramos el primer elemento y tomamos como nuestro arreglo a ese único elemento, por tanto, un arreglo de un elemento está ordenado siempre. Ahora miramos el segundo elemento y tomamos como nuestro arreglo esas dos celdas: la primera y la segunda. De este modo comparamos el segundo elemento con el primero, si están ordenados pues seguimos, sino los intercambiamos de lugar para que queden ordenados.


Ahora miramos el tercer elemento, tomando entonces como arreglo a esas tres celdas. Entonces comparamos el tercer elemento con el segundo, si están ordenados seguimos, sino los intercambiamos de lugar. En ese caso, ahora miramos el segundo elemento (que antes era tercero) y lo comparamos con el primero, si están ordenados lo dejamos así y sino los intercambiamos.


De este modo en cada pasada vamos ordenando una porción del arreglo, y nos vamos extendiendo hasta abarcarlo por completo. Veámoslo en un ejemplo donde queremos ordenar una lista de números en forma ascendente:


La lista inicial es: 45, 52, 21, 37, 49, 72, 14. Tenemos un arreglo entonces de 7 celdas.


Para continuar con el ejemplo marcaré en rojo al elemento que estamos analizando, en verde la lista ya ordenada y en negro lo que aún queda por ordenar.


En realidad nunca se analiza el primer elemento por sí solo ya que siempre estará ordenado, por lo que se comienza a mirar desde el segundo elemento.


Pasada número 1:


45, 52, 21, 37, 49, 72, 14 → Miramos al 52 y lo comparamos con el anterior, o sea 45. Como están ordenados entre ellos, los dejamos así y continuamos.


Entonces tenemos que 45 y 52 forman un arreglo ordenado: 45, 52, 21, 37, 49, 72, 14.


Pasada número 2:


Decimos que los dos primeros elementos están en orden relativo ya que eventualmente modificaremos esa lista para que una mayor quede ordenada. Debemos ver el tercer elemento:


45, 52, 21, 37, 49, 72, 14 → Comparamos el 21 con el 52, como no están ordenados entre sí, los intercambiamos de lugar para que queden en orden entre ellos. Nos quedamos entonces con esto:


45, 21, 52, 37, 49, 72, 14 → Ahora, como intercambiamos lugares, debemos comparar el 21 con su anterior. Vemos que no están ordenados entre ellos, entonces hacemos un nuevo intercambio y tenemos esto:


21, 45, 52, 37, 49, 72, 14 → El 21 quedó en la primera posición y por ende no hay más para comparar, entonces tenemos esto:


21, 45, 52, 37, 49, 72, 14.


Pasada número 3:


21, 45, 52, 37, 49, 72, 14 → Estamos analizando ahora al 37, entonces lo comparamos con el anterior a él, o sea el 52. Como no están ordenados los intercambiamos:


21, 45, 37, 52, 49, 72, 14 → Ahora comparamos al 37 con su anterior actual, o sea el 45, como no están ordenados los intercambiamos.


21, 37, 45, 52, 49, 72, 14 → Habiendo hecho otro intercambio comparamos entonces el 37 con su anterior, o sea el 21. Ya están ordenados por lo que dejamos la lista así:


21, 37, 45, 52, 49, 72, 14 → Como pueden ver, el arreglo formado por los primeros cuatro números está ordenado. Quedan tres por ordenar.




Pasada número 4:


21, 37, 45, 52, 49, 72, 14 → Continuamos con el método, entonces comparamos el número actual que es 49 con su anterior que es 52. Como no están ordenados entre ellos los intercambiamos.


21, 37, 45, 49, 52, 72, 14 → Ahora comparamos el 49 con su anterior que es el 45, como están ordenados los dejamos así, obteniendo esta lista.


21, 37, 45, 49, 52, 72, 14.


Pasada número 5:


21, 37, 45, 49, 52, 72, 14 → Seguimos con esto y pues, más de lo mismo. En este caso el 72 ya está ordenado con su anterior por lo que no tenemos nada por hacer.


Pasada número 6:


21, 37, 45, 49, 52, 72, 14 → En este caso el 14 se irá moviendo hasta la primera posición obteniendo así este arreglo: 14, 21, 37, 45, 49, 52, 72. Como ven, está ordenado.


¿Cuál sería el mejor caso para este algoritmo? Pues que el arreglo ya esté ordenado. Para este caso tendríamos que recorrer todo el arreglo sin hacer intercambios. En un arreglo de n cantidad de elementos, tendríamos n cantidad de consultas, una por cada celda, por tanto este algoritmo tendría orden n, O(n).


¿Cuál sería el peor caso? Pues que el arreglo, además de estar desordenado, esté justamente en orden inverso al que debería estar. En este caso se harían n consultas n cantidad de veces, o sea n*n cantidad de consultas. Esto es igual que n^2 (n cuadrado, o n elevado al cuadrado) cantidad de consultas, entonces el orden es O(n^2).


Como podrán observar, no es un algoritmo muy eficiente, sin embargo la mayoría de los algoritmos de ordenación que son relativamente sencillos tienen un O(n^2). Existen otros con orden menor, pero son complejos y pues, no los veremos aquí.


Vamos al código fuente de este algoritmo en Modula:

PROCEDURE OrdenarArreglo(VAR arr: ARRAY OF INTEGER);
VAR
   i, j, elem : INTEGER;
 
BEGIN
	FOF i:= 1 TO MAX_LARGO_ARREGLO DO
		elem:= arr[i];
   		j:= i-1;
   		WHILE ((j>= 0) AND (insertion[j]> index)) DO
			arr[j+1]:= arr[j];
     			j:=j - 1;
    		END;
   		arr[j+1]:= elem;
	END; 
END OrdenarArreglo;

Les dejo como ejercicio que analicen este algoritmo, no es complejo si han entendido mi explicación previa.
-----------------------------------------------------------------------------------


Ordenación por Selección:


Para empezar les diré que este algoritmo tiene O(n^2) en todos los casos siempre. Sin embargo es bastante simple de implementar.


La idea es la siguiente: Supongan que se quiere ordenar un arreglo de forma ascendente, tal como hicimos con el método de Ordenación por Inserción. Buscamos el elemento más grande de todo el arreglo y lo ponemos en la última posición ya que obviamente ese es su lugar correcto.


Ya que la última posición tiene a quién le corresponde, buscaremos ahora el mayor elemento desde el principio hasta la penúltima posición. Cuando lo encontramos lo ponemos en el penúltimo lugar del arreglo.


Ahora buscamos el mayor hasta el antepenúltimo lugar y repetimos el procedimiento. De este modo, al terminar, el arreglo habrá quedado ordenado.


Otra forma sería al revés, buscar el menor elemento y colocarlo al principio. Cualquiera de ambas es correcta. Para nuestro ejemplo lo haremos como describí.


Supongan entonces que tenemos el mismo arreglo inicial: 45, 52, 21, 37, 49, 72, 14.


Entonces buscamos el mayor elemento. Esto siempre nos obliga a recorrer todo el arreglo a ordenar porque es imposible saber qué elemento es el mayor si no los hemos visto todos. Claramente necesitamos un algoritmo para buscar el mayor elemento de muchos. Esto no es más que la aplicación del ejercicio 2 de la secuencia FOR que les había planteado en el curso de Pascal y que tantos problemas les había causado a muchos.


Entonces, para nuestro ejemplo buscamos el mayor elemento y encontramos que es el 72:


45, 52, 21, 37, 49, 72, 14 → Entonces intercambiamos el 72 hacia el último lugar.


45, 52, 21, 37, 49, 14, 72 → Con esto ese valor ya está ordenado respecto a los demás.


Ahora buscamos el mayor elemento pero sin mirar la última posición porque ya está ordenada. Entonces encontramos que el mayor elemento ahora es el 52:


45, 52, 21, 37, 49, 14, 72 → Intercambiamos el 52 con el 14 para que el 52 quede donde debe ir.


45, 14, 21, 37, 49, 52, 72 → De este modo los dos últimos lugares están ordenados respecto a todos los demás. Repetimos entonces el procedimiento y encontramos que el mayor valor ahora es el número 49:


45, 14, 21, 37, 49, 52, 72 → Como está donde debe ir, lo dejamos ahí y continuamos.


Esto se repite hasta llegar a la primera posición del arreglo, donde ya no habrá más nada que ordenar.


Para la solución en Modula tendremos dos códigos, uno con una función llamada EncontrarMaximo que nos devolverá el índice indicando la posición del máximo elemento en un arreglo acotado hasta una posición k; y otro con el algoritmo de ordenación, el cual utilizará a la función EncontrarMaximo para realizar sus tareas.


Por ejemplo, para este caso:


45, 14, 21, 37, 49, 52, 72 → Debemos buscar el máximo tomando en cuenta hasta la posición número 4 del arreglo ya que las últimas 3 están ordenadas. Entonces, a nuestra función le pasaremos el arreglo y la posición hasta la que tiene que buscar:

PROCEDURE EncontrarMaximo(arr: ARRAY OF CHAR; ultimo: INTEGER): CARDINAL;
VAR j, max: CARDINAL;
BEGIN
	max := 1;
	FOR j := 2 TO ultimo DO
		IF arr[j] > arr[max] THEN
			max := j;
		END;
	END;
	maximo := max;
END EncontrarMaximo;

Veamos entonces cómo ordenarlo:

PROCEDURE OrdenarArreglo(VAR arr: ARRAY OF INTEGER);
VAR i, mayor, temp: INTEGER;
BEGIN
	FOR i := N TO 2 BY -1 DO
		mayor := EncontrarMaximo(arr,i);
		temp := arr[mayor];
		arr[mayor] := arr[i];
		arr[i] := temp;
	END;
END OrdenarArreglo;

Cualquiera de estos dos algoritmos son sencillos por lo cual no deberían tener problemas con ellos.




NOTA: Los algoritmos que se han mostrado aquí, tanto para buscar como para ordenar arreglos, funcionan en memoria RAM directamente. Existen otros que funcionan sobre el disco duro y demás, logrando mejorar el orden de ejecución, sin embargo no los veremos aquí porque no trabajaremos con este tipo de almacenamiento; además dichos algoritmos son mucho más complejos que los que vimos aquí.


Ustedes deben acostumbrarse a ellos cuando deban ordenar y buscar sobre estructuras de acceso directo como los arreglos. Con esto quiero decir que, por ejemplo, para ordenar una lista encadenada o buscar sobre ella, no podemos utilizar estos algoritmos necesitamos acceder directamente las celdas, y una lista no nos permite eso. Dicho más claramente, si en un arreglo queremos ir a la celda número n, simplemente escribimos variable_arreglo[n] y tenemos el valor en esa celda; pero en una lista no podemos acceder directamente a una posición, sino que para ir a la celda n deberíamos comenzar desde el principio y recorrer celda por celda hasta llegar a la posición n.


----------------------------------------------------------------------------------


En la próxima lección, que no será dentro de mucho, les dejaré los ejercicios para que practiquen un poco. Igualmente ya tienen suficiente material como para realizar los ejercicios de Pascal en Modula.


Saludos.

[donkingg]

Excelente articulo Vlady. recuerdo en mi secundario el viejo y querido burbujeo, primer algoritmo que me enseñaron para ordenar una lista!.

Saludos!

[Kryptonyte]

¿En el secundario enseñan eso ahora, y lo enseñaban hace X años? ¿País? ¿Otros datos? Claro, en mi época ni existían las computadoras. Después de tantas noticias negativas sobre la educación, una positiva.

[donkingg]

¿En el secundario enseñan eso ahora, y lo enseñaban hace X años? ¿País? ¿Otros datos? Claro, en mi época ni existían las computadoras. Después de tantas noticias negativas sobre la educación, una positiva.

Hola Kryptonyte, me los enseñaron en el industrial Otto Krause, de Capital Federal Argentina, ahí me recibí de técnico en computación.
Cada vez que paso por mi colegio lo recuerdo con mucho cariño por la gran educación que nos dieron.

Saludos!.

[LUK1LL45]

Excelente tutorial Vlady, más claro imposible.