Métodos de ordenamiento de vectores PDF

Preview

Summary

Se describen las distintas formas de ordenar un vector usando el lenguaje de programación C++ tales como Quick Sort, Merge Sort, entre otros....

Description

Se pide lo siguiente: 1) ¿Qué es el Análisis Algorítmico? 2) Definir Orden de un Algoritmo. 3) Analizar los siguientes métodos de ordenamiento: a. Intercambio o burbuja mejorado b. Inserción o método de la baraja c. Selección o método sencillo d. Rápido o QuickSort e. Por Mezcla o MergeSort

Para método: o Explicar la estrategia utilizada. o Programar en Dev-C++ el método. El programa debe permitir el ingreso de un vector, ordenar el mismo a través del método en cuestión, mostrar el vector ordenado. 

Orden del algoritmo en el peor caso, mejor caso y caso promedio.

Introducción

La resolución práctica de un problema exige por una parte un algoritmo o método de resolución y por otra un programa o codificación de aquel en un ordenador real. Ambos componentes tienen su importancia; pero la del algoritmo es absolutamente esencial, mientras que la codificación puede muchas veces pasar a nivel de anécdota. A efectos prácticos o ingenieriles, nos deben preocupar los recursos físicos necesarios para que un programa se ejecute. Aunque puede haber muchos parámetros, los más usuales son el tiempo de ejecución y la cantidad de memoria (espacio). Ocurre con frecuencia que ambos parámetros están fijados por otras razones y se plantea la pregunta inversa: ¿cuál es el tamaño del mayor problema que puedo resolver en T segundos y/o con M bytes de memoria? En lo que sigue nos centraremos casi siempre en el parámetro tiempo de ejecución, si bien las ideas desarrolladas son fácilmente aplicables a otro tipo de recursos.

1.

Análisis algorítmico

El uso del análisis algorítmico permite generalizar el número de operaciones que requiere un algoritmo para encontrar la solución a un problema. Dicho en otras palabras, su implementación nos lleva a:  

Determinar tiempos de respuesta (runtime). Determinar recursos computacionales.

La característica básica que debe tener un algoritmo es que sea correcto, es decir, que produzca el resultado deseado en tiempo finito. Adicionalmente puede interesarnos que sea claro, que este bien estructurado, que sea fácil de usar, que sea fácil de implementar y que sea eficiente. Entendemos por eficiencia de un algoritmo la cantidad de recursos de cómputo que requiere; es decir, cual es su tiempo de ejecución y qué cantidad de memoria utiliza. A la cantidad de tiempo que requiere la ejecución de un cierto algoritmo se le suele llamar coste en tiempo mientras que a la cantidad de memoria que requiere se le suele llamar coste en espacio. Para realizar el análisis de un algoritmo, es necesario:   

Conocer la complejidad del problema que resuelve el algoritmo Conocer la dimensión de la entrada (número de elementos) Determinar el número de operaciones a realizar.

La complejidad de un algoritmo se representa a través de una función matemática, ya sean polinomios, logaritmos, exponentes, etc. A través de un análisis teórico, se pueden obtener funciones que representen el número de operaciones, independientemente de cómo se implementaron. Es evidente que conviene buscar algoritmos correctos que mantengan tan bajo como sea posible el consumo de recursos que hacen del sistema, es decir, que sean lo más eficientes posible. Cabe hacer notar que el concepto de eficiencia de un algoritmo es un concepto relativo, esto quiere decir que ante dos algoritmos correctos que resuelven el mismo problema, uno es más eficiente que otro si consume menos recursos. Por tanto, podemos observar que el concepto de eficiencia y en consecuencia el concepto de coste nos permitirá comparar distintos algoritmos entre ellos.

Ventajas:  Elección de algoritmos eficientes para resolver problemas específicos.  No depende de lenguajes de programación ni de hardware Desventajas:  Para muchos casos, en análisis no es trivial

2.

Orden de un algoritmo

Un algoritmo de ordenamiento es un algoritmo que pone elementos de una lista o un vector en una secuencia dada por una relación de orden, es decir, el resultado de salida ha de ser una permutación —o reordenamiento— de la entrada que satisfaga la relación de orden dada. Las relaciones de orden más usadas son el orden numérico y el orden lexicográfico. Ordenamientos eficientes son importantes para optimizar el uso de otros algoritmos (como los de búsqueda y fusión) que requieren listas ordenadas para una ejecución rápida. También es útil para poner datos en forma canónica y para generar resultados legibles por humanos. Desde los comienzos de la computación, el problema del ordenamiento ha atraído gran cantidad de investigación, tal vez debido a la complejidad de resolverlo eficientemente a pesar de su planteamiento simple y familiar. Por ejemplo, BubbleSort (método de la burbuja) fue analizado desde 1956. Aunque muchos puedan considerarlo un problema resuelto, nuevos y útiles algoritmos de ordenamiento se siguen inventando hasta el día de hoy. Los algoritmos de ordenamiento son comunes en las clases introductorias a la computación, donde la abundancia de algoritmos para el problema proporciona una gentil introducción a la variedad de conceptos núcleo de los algoritmos, como notación de O mayúscula, algoritmos divide y vencerás, estructuras de datos, análisis de los casos peor, mejor, y promedio, y límites inferiores. En nuestro caso para el análisis de algoritmos usaremos los términos peor caso, mejor caso y caso promedio tienen los siguientes significados: Mejor caso: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una menor complejidad computacional. Peor caso: se refiere a la situación inicial de los datos que genera una ejecución del algoritmo con una complejidad computacional mayor. Caso promedio: la situación inicial de los datos no sigue ningún patrón preestablecido que aporte ventajas o desventajas. Se puede considerar, por tanto, la situación típica de ejecución del algoritmo. La complejidad está determinada por el número de comparaciones y de asignaciones entre elementos del conjunto que se realiza en una implementación específica del algoritmo. Por ejemplo, en el algoritmo de Inserción directa el caso mejor se presenta cuando el conjunto de elementos a ordenar se encuentra ya ordenado. En ese caso, los valores representativos son los siguientes: C_ {min}=n-1 M_ {min}=2(n-1)

donde C_{min}y M_{min}} son el número mínimo de comparaciones y el número mínimo de movimientos entre elementos del conjunto de datos del algoritmo de Inserción directa.

3. a. burbuja

Intercambio o metodo de la

Este metodo es el mas sencillo probablemente. Consiste en ciclar repetidamente a traves de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que esta en la siguiente posicion se intercambian.

Se declaran variables, y se carga el vector:

Muestra el vector desordenado

Realiza el metodo de intercambio, utilizando una variable auxiliar para realizar el intercambio.

Vuelve a mostrar el vector ordenado:

b.

Ordenamiento por Inserción

Este es el algoritmo más sencillo probablemente. Ideal para empezar. Consiste en ciclar repetidamente a través de la lista, comparando elementos adyacentes de dos en dos. Si un elemento es mayor que el que está en la siguiente posición se intercambian. ¿Sencillo no? Una manera de realizar eso, o como dar un ejemplo podría ser la siguiente manera como para demostrar como funcionaria el algoritmo así todos puedan entenderlo Vamos a ver un ejemplo. Esta es nuestra lista: 4-3-5-2-1 Tenemos 5 elementos. Es decir, toma el valor 5. Comenzamos comparando el primero con el segundo elemento. 4 es mayor que 3, así que intercambiamos. Ahora tenemos: 3-4-5-2-1 Ahora comparamos el segundo con el tercero: 4 es menor que 5, así que no hacemos nada. Continuamos con el tercero y el cuarto: 5 es mayor que 2. Intercambiamos y obtenemos: 3-4-2-5-1 Comparamos el cuarto y el quinto: 5 es mayor que 1. Intercambiamos nuevamente: 3-4-2-1-5 Repitiendo este proceso vamos obteniendo los siguientes resultados: 3-2-1-4-5 2-1-3-4-5

1-2-3-4–5 Estabilidad: Este algoritmo nunca intercambia registros con claves iguales. Por lo tanto, es estable. Requerimientos de Memoria: Una variable adicional para realizar los intercambios. Tiempo de Ejecución: Para una lista de n elementos el ciclo externo se ejecuta n1 veces. El ciclo interno se ejecuta como máximo una vez en la primera iteración, 2 veces en la segunda, 3 veces en la tercera, etc. Esto produce una complejidad O(n2).

Ventajas: 

Fácil implementación.



Requerimientos mínimos de memoria.

Desventajas: 

Lento.



Realiza numerosas comparaciones.

Este también es un algoritmo lento, pero puede ser de utilidad para listas que están ordenadas o semiordenadas, porque en ese caso realiza muy pocos desplazamientos.

El algoritmo que se usa es básico y muy fácil de programar

c.

Ordenamiento por selección

Este algoritmo también es sencillo. Consiste en lo siguiente: 

Buscas el elemento más pequeño de la lista.



Lo intercambias con el elemento ubicado en la primera posición de la lista.



Buscas el segundo elemento más pequeño de la lista.



Lo intercambias con el elemento que ocupa la segunda posición en la lista.



Repites este proceso hasta que hayas ordenado toda la lista.



Un ejemplo de cómo trabaja el algoritmo seria de la siguiente manera Vamos a ordenar la siguiente lista (la misma del ejemplo anterior). 4-3-5-2-1 Comenzamos buscando el elemento menor entre la primera y última posición. Es el 1. Lo intercambiamos con el 4 y la lista queda así: 1-3-5-2-4 Ahora buscamos el menor elemento entre la segunda y la última posición. Es el 2. Lo intercambiamos con el elemento en la segunda posición, es decir el 3. La lista queda así: 1-2-5-3-4 Buscamos el menor elemento entre la tercera posición y la última. Es el 3, que intercambiamos con el 5: 1-2-3-5-4 El menor elemento entre la cuarta y quinta posición es el 4, que intercambiamos con el 5: 1-2-3-4-5 ¡Y terminamos! Ya tenemos nuestra lista ordenada. ¿Fue fácil no?

Estabilidad: Aquí discrepo con un libro de la bibliografía que dice que no es estable. Yo lo veo así: si tengo dos registros con claves iguales, el que ocupe la posición más baja será el primero que sea identificado como menor. Es decir que será el primero en ser desplazado. El segundo registro será el menor en el siguiente ciclo y quedará en la posición adyacente. Por lo tanto, se mantendrá el orden relativo. Lo que podría hacerlo inestable sería que el ciclo que busca el elemento menor revisara la lista desde la última posición hacia atrás. Opinamos que es estable, pero para hacerle caso al libro vamos a decir que no es estable. Requerimientos de Memoria: Al igual que el ordenamiento burbuja, este algoritmo sólo necesita una variable adicional para realizar los intercambios. Tiempo de Ejecución: El ciclo externo se ejecuta n veces para una lista de n elementos. Cada búsqueda requiere comparar todos los elementos no clasificados. Luego la complejidad es O(n2). Este algoritmo presenta un comportamiento constante independiente del orden de los datos. Luego la complejidad promedio es también O(n2).

Ventajas:    

Fácil implementación. No requiere memoria adicional. Realiza pocos intercambios. Rendimiento constante: poca diferencia entre el peor y el mejor caso.

Desventajas:  

Lento. Realiza numerosas comparaciones.

Este es un algoritmo lento. No obstante, ya que sólo realiza un intercambio en cada ejecución del ciclo externo, puede ser una buena opción para listas con registros grandes y claves pequeñas. Si miras el programa de demostración notarás que es el más rápido en la parte gráfica (por lo menos en un PC lento y con una tarjeta gráfica mala como el mío x-|). La razón es que es mucho más lento dibujar las barras que comparar sus largos (el desplazamiento es más costoso que la comparación), por lo que en este caso especial puede vencer a algoritmos como Quicksort.

Una vista al código que se utiliza sería el siguiente

d.

Rápido o Quick sort

Este método de ordenamiento, es un algoritmo basado en la técnica “divide y vencerás” que permite ordenar n elementos en un tiempo proporcional a n log n. Es la técnica as rápida. El algoritmo fundamental es: 1. Elegir un elemento de la lista a ordenar, se le llama a éste pivote. 2. Busca la posición que le corresponde en la lista ordenada. 3. Acomodas los elementos de la lista a cada lado del pivote, de un lado va a tener los menores que él, y del otro lado los mayores a el. En este momento el pivote separa la lista en dos sublistas.

4. Repetir este proceso de forma recursiva para cada sublistas mientras estas contengan más de un elemento. Una vez terminado este proceso, todos los elementos quedan ordenados. La eficiencia del algoritmo depende de la posición en la que termine el pivote elegido. Se utilizan dos índices i (contador de izquierda) y j (contador de la derecha). Y el algoritmo es: 1.Recorrer la lista simultáneamente con i y j: por la izquierda con i (desde el primer elemento) y por la derecha con j (desde el último elemento). 2. Cuando lista [i] sea mayor que el pivote y lista [j] sea menor, los intercambias. 3. Repite esto hasta que se crucen los índices. 4. El punto donde se cruzan los índices, es la posición adecuada para colocar el pivote. Se utilizaran tres funciones, la primera hara el intercambio, la segunda el metodo a aplicar y la tercera lo mostrara al vector ordenado.

Función de intercambio

Función del método Quick sort

función para mostrar el vector ordenado

e. Sort

Método de ordenamiento por Merge

El algoritmo de ordenamiento por mezcla (merge sort) es un algoritmo de ordenamiento externo estable de Complejidad O (n log n). Este método aplica la técnica divide-y-vencerás, dividiendo la secuencia de datos en dos subsecuencias hasta que las subsecuencias tengan un único elemento, luego se ordenan mezclando dos subsecuencias ordenadas en una secuencia ordenada, en forma sucesiva hasta obtener una secuencia única ya ordenada. Fue desarrollado en 1945 por John Von Neumann. Este algoritmo también es llamado de Intercalación o combinación, debido que combina (intercala) dos estructuras previamente ordenadas.

Divide y vencerás El método que usado para resolver este problema se llama divide y vencerás, y se aplica en las situaciones en las que vale el siguiente principio: Para obtener una solución es posible partir el problema en varios subproblemas de tamaño menor, resolver cada uno de esos subproblemas por separado

aplicando la misma técnica (en nuestro caso ordenar por mezcla cada una de las dos sublistas), y finalmente juntar estas soluciones parciales en una solución completa del problema mayor (en nuestro caso la intercalación ordenada de las dos sublistas ordenadas). Como siempre sucede con las soluciones recursivas, debemos encontrar un caso base en el cual no se aplica la llamada recursiva. Si la lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer). Además debemos asegurar que siempre se alcanza el caso base, y en este caso aseguramos eso porque la lista original se divide siempre en mitades cuando su longitud es mayor que 1.

Procedimiento Conceptualmente, el ordenamiento por mezcla funciona de la siguiente manera: 1.Si la longitud de la lista es 0 ó 1, entonces el arreglo ya está ordenado. De lo contrario, de lo contrario hacer lo siguiente: 2.Dividir la lista al medio, formando dos sublistas de (aproximadamente) el mismo tamaño cada una. 3.Ordenar cada una de esas dos sublistas (usando este mismo método). 4.Una vez que se ordenaron ambas sublistas, intercalarlas de manera ordenada.

Por ejemplo, si la lista original es [6, 7, -1, 0, 5, 2, 3, 8] deberemos ordenar recursivamente [6, 7, -1, 0] y [5, 2, 3, 8] con lo cual obtendremos [-1, 0, 6, 7] y [2, 3, 5, 8]. Si intercalamos ordenadamente las dos listas ordenadas obtenemos la solución buscada: [-1, 0, 2, 3, 5, 6, 7, 8]. Si representamos esas operaciones en una imagen, puedes notar que se forma un árbol, donde, partiendo de las hojas (son los elementos terminales del árbol), se van a ordenar los nodos padres, por medio de la mezcla entre sus dos hijos, hasta llegar al nodo raíz

Estructura del algoritmo Una vez que tenemos nuestro vector a ordenar, diseñamos la función merge_sort (lista): 1.

Si lista es pequeña (vacía o de tamaño 1) ya está ordenada y no hay nada que hacer. Se devuelve lista tal cual.

2.

De lo contrario: o

medio = len(lista)/2

o

izq = merge_sort(lista[:m])

o

der = merge_sort(lista[m:])

o

Se devuelve merge (izq, der).

Falta sólo diseñar la función merge que realiza la intercalación ordenada de dos listas ordenadas (dadas dos listas ordenadas se debe obtener una nueva lista que resulte de intercalar a ambas de manera ordenada).

Diseñamos la función merge (lista1, lista2): 1.

Utilizaremos dos índices, i y j, para recorrer cada una de las dos listas.

2.

Utilizaremos una tercera lista, resultado, donde almacenaremos el resultado.

3.

Mientras i sea menor que el largo de lista1 y j menor que el largo de lista2, significa que hay elementos para comparar en ambas listas. o

Si el menor es el de lista1: agregar el elemento i de lista1 al final del resultado. Avanzar el índice i.

o

de lo contrario: agregar el elemento j de lista2 al final del resultado. Avanzar el índice j.

4.

Una vez que una de las dos listas se termina, simplemente hay que agregar todo lo que queda en la otra al final del resultado.

A continuación, se muestra un prototipo del algoritmo:

Ventajas y desventajas

Ventajas 

Método estable de ordenamiento mientras la operación de mezclas (merge) esté bien implementada.



Este algoritmo es efectivo para conjuntos de datos que se puedan acceder como arreglos, vectores y listas ligadas.



Rápido.

Desventajas 

Su principal desventaja radica en que está definido recursivamente y su implementación no recursiva emplea una pila, por lo que requiere un espacio adicional de memoria para almacenarla.

Resumen del análisis del método   

Estabilidad: Sí es estable. Requerimientos de Memoria: Se necesita memoria auxiliar del mismo tamaño de los conjuntos a mezclar. Tiempo de Ejecución: O (n log n).

Conclusiones Antes de realizar un programa conviene elegir un buen algoritmo, donde por bueno entendemos que utilice pocos recursos, siendo usualmente los más importantes el tiempo que lleve ejecutarse y la cantidad de espacio en memoria que requiera. Es engañoso pensar que todos los algoritmos son "más o menos iguales" y confiar en nuestra habilidad como programadores para convertir un mal algoritmo en un producto eficaz. Es asimismo engañoso confiar en la creciente potencia de las máquinas y el abaratamiento de las mismas como remedio de todos los problemas que puedan aparecer. En el análisis de algoritmos se considera usualmente el caso peor, si bien a veces conviene analizar igualmente el caso mejor y hacer alguna estimación sobre un caso promedio. Para problemas pequeños es cierto que casi todos los algoritmos son "más o menos iguales", primando otros aspectos como esfuerzo de codificación, legibilidad, etc. Los órdenes de complejidad sólo son importantes para grandes problemas....