ORDENACIÓN RÁPIDA (QUICKSORT)


ORDENACIÓN RÁPIDA (QUICKSORT)

Este algoritmo divide en array en dos subarray, que se pueden ordenar de modo independiente.
Se selecciona un elemento específico del array arreglo[centro] llamado pivote. Luego, se debe re situar los demás elementos de la lista a cada lado del pivote, de manera que a un lado queden todos los menores que él, y al otro los mayores. Los elementos iguales al pivote pueden ser colocados tanto a su derecha como a su izquierda, dependiendo de la implementación deseada.

En este momento, el pivote ocupa exactamente el lugar que le corresponderá en la lista ordenada. Finalmente, se divide el array original en dos subarrays que se ordenarán de modo independiente mediante llamadas recursivas del algoritmo.

Comentarios

Publicar un comentario

Entradas más populares de este blog

MÉTODO DE BINSORT

              MÉTODO DE BINSORT Este método, también llamado clasificación por urnas, persigue conseguir funciones de tiempo de ejecución menores de O(n log n), para ordenar una secuencia de n elementos siempre que se conozca algo acerca del tipo de las claves por las que se están ordenando. Supóngase que se tiene un vector v[] de registros, se quiere ordenar respecto un campo clave de tipo entero, además se sabe que los valores de las claves se encuentran en el rango de 1 a n, sin claves duplicadas y siendo n el número de elementos. En estas circunstancias es posible colocar los registros ordenados en un array auxiliar t[] mediante este bucle: for 1:= 1 to n do        t[v[i].clave] = v[i]; Sencillamente determina la posición que le corresponde según el valor del campo clave. El bucle lleva un tiempo de ejecución de complejidad O(n). Esta ordenación tan sencilla que se ha expuesto es un caso particula...
Leer más

MÉTODO DE RADIXSORT

     MÉTODO DE RADIXSORT Este método puede considerarse como una generalización de la clasificación por urnas. Aprovecha la estrategia de la forma más antigua de clasificación manual, consistente en hacer diversos montones  de fichas, cada uno caracterizado por tener sus componentes un mismo dígito (letra, si es alfabética) en la misma posición; estos montones se recogen en orden ascendente y se reparte de nuevo en montones según el siguiente dígito de la clave.
Leer más

MÉTODOS DE BÚSQUEDA Y ORDENAMIENTO

MÉTODOS DE BÚSQUEDA Y ORDENAMIENTO Ordenación y búsqueda, son operaciones básicas en el campo de la documentación y en las que, según señalan las estadísticas, las computadoras emplean la mitad de su tiempo. 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érico para los números y alfabético para los caracteres) ascendente o descendente. La búsqueda de información es, al igual que la ordenación, otra operación muy frecuente en el tratamiento de información.  La búsqueda es una actividad que se realiza diariamente en cualquier aspecto de la vida: búsqueda de palabras en un diccionario, nombres en una guía telefónica, localiza...
Leer más