QuickSort (Ordenamiento Rápido) INTEGRANTES: 1. RESUMEN: En este informe detallaremos principalmente un algoritmo de
Views 66 Downloads 0 File size 164KB
QuickSort (Ordenamiento Rápido)
INTEGRANTES:
1. RESUMEN:
En este informe detallaremos principalmente un algoritmo de ordenación que es probablemente el más utilizado de todos, nos referimos a la Ordenación Rápida (QUICKSORT). El algoritmo básico fue creado en 1960 por C.A.R. Hoare y publicado en 1962 y desde entonces ha sido estudiado objeto de numerosos estudios. El Quicksort es popular porque a pesar de su no tan fácil implementación, proporciona unos buenos resultados generales (funciona bien en una amplia diversidad de situaciones) y en muchos casos consume menos recursos que cualquier otro método de ordenación, por cual el método ha sido posiblemente calificado como el mas pequeño código, más rápido, más elegante, más interesante y eficiente de los algoritmos conocidos de ordenación. La idea central de este algoritmo consiste en los siguiente: - Se toma un elemento x de una posición cualquiera del arreglo. - Se trata de ubicar a x en la posición correcta del arreglo, de tal forma que todos los elementos que se encuentran a su izquierda sean menores o iguales a x y todos los -elementos que se encuentren a su derecha sean mayores o iguales a x. - Se repiten los pasos anteriores pero ahora para los conjuntos de datos que se encuentran a la izquierda y a la derecha de la posición correcta de x en el arreglo. El análisis ha sido comprobado por una extensa experiencia empírica hasta el punto de convertirse en el método elegido en una gran variedad de aplicaciones prácticas de ordenación teniendo así una complejidad en el mejor caso de grado n.logn y peor caso de grado n 2 Desde su creación han intentado y analizado nuevas versiones del algoritmo, pero es fácil decepcionarse porque este algoritmo esta bien equilibrado, que las mejoras en una parte del programa pueden estar mas que compensados por las consecuencias de un mal rendimiento de otra pero por eso no mejoran sustancialmente a Quicksort.
2. INTRODUCCIÓN.
Ordenación y Búsqueda son operaciones básicas en el campo de la documentación y en las que según señalan estadísticas, las computadoras emplean la mitad de su tiempo. Aunque su uso puede ser con vectores y con archivos, nos referiremos a vectores. La ordenación (clasificación) es la operación de organizar un conjunto de datos en algún orden dado, tal como creciente o decreciente en datos numéricos, o bien en orden alfabético directo o inverso. Operaciones típicas de ordenación son: lista de números, archivos de clientes de banco, nombres de una agenda telefónica, etc. En síntesis la ordenación significa poner objetos en orden (orden numéricos para los números y alfabético para los caracteres) ascendente o descendente. Por ejemplo, las clasificaciones de los equipos de fútbol, se pueden organizar en orden alfabético creciente/decreciente o bien por su puntaje obtenido ascendente/descendente. El propósito final de la clasificación es facilitar la manipulación de datos en un vector. Existen diversos métodos de ordenación o clasificación, con diferentes ventajas e inconvenientes donde debemos tener en cuenta las eficiencias en cuanto al tiempo siendo método quicksort uno de ellos, que abarcaremos principalmente aplicados a vectores pero se pueden extender a matrices o tablas, considerando la ordenación respecto a fila o columna, quicksort nos permitirá ordenar vectores con un gran número de elementos y manipular dicho vector. 3. CONTENIDO: 3.1.ORIGEN. Inventado por Sir Charles Antony Richard Hoare (científico Británico en computación) en 1960,
cuando visitó la Universidad de Moscú cuando era estudiante . Él creó el “Quicksort” al intentar traducir un diccionario de inglés para ruso, ordenando las palabras, teniendo cómo objetivo reducir el problema original en subproblemas que puedan ser resueltos más fácil y rápidamente. Fue publicado en 1962 después de una serie de afinamientos. 3. 2.DEFINICION. El ordenamiento rápido (quicksort en inglés) es un algoritmo basado en la técnica de divide y vencerás, que permite, en promedio, ordenar “n” elementos en un tiempo proporcional a n*log(n). Esta es la técnica de ordenamiento más rápida conocida. El algoritmo original es recursivo, pero se utilizan versiones iterativas para mejorar su rendimiento. • Dividir: el arreglo se particiona en dos sub-arreglos no vacíos, tal que cada elemento de un sub-arreglo sea menor o igual a los elementos del otro sub-arreglo. • Conquistar: los dos arreglos son ordenados llamando recursivamente a quicksort. • Combinar: Como cada arreglo ya está ordenado, no se requiere trabajo adicional. 3. 3. CARACTERISTICAS. • Este método se basa en la táctica “divide y vencerás”: consiste en dividir un problema en subproblemas y luego juntar las respuestas de estos subproblemas para obtener la solución al problema central (subdividiendo el array en arrays más pequeños y ordenar estos). • Es considerado entre los más rápidos y eficientes de los métodos de ordenación interna. • El tiempo en marcha del algoritmo esencialmente depende de la opción del elemento del pivote. • Posible reducción de desempeño debido a uso de recursos. • Tiempo de ejecución depende de los datos de entrada 3.4. ALGORITMO. 1. Elegimos un elemento v (llamado pivote) del array de datos. 2. Particionados el array de datos A en dos arrays: • A1 = Los elementos del array que se encuentran a la izquierda del pivote. -aquí se buscaran los numero mayores que el pivote.
-una vez ubicado el mayor de la izquierda tan solo se guarda su posición para luego usarla. • A2 = Los elementos del array que se encuentran a la derecha del pivote. -aquí se buscaran los numero menores que el pivote. -una vez ubicado el menor de la derecha tan solo se guarda su posición para luego usarla. 3. Luego de tener las posiciones se procederá a intercambiar sus contenidos. 4. Aplicamos la recursión sobre A1 y A2 5. Realizamos el último paso de "divide y vencerás" que es unir todas las soluciones Para que formen el array A ordenado. DIAGRAMA DE FLUJO.
PSEUDOCODIGO. INICIO Llenar (A); Algoritmo quicksort (A, inf, sup) i inf j sup x A [ (inf +sup) div 2] mientras i = < j hacer mientras A[ i ]< x hacer i i +1 fin _ mientras mientras A[ j ]> x hacer j j -1 fin _ mientras si i =