ALGORITMO QUICKSORT



      ALGORITMO QUICKSORT

La primera etapa en el algoritmo de partición es obtener el elemento pivote; una vez que se ha seleccionado se ha de buscar el sistema para situar en la sublista izquierda todos los elementos menores que el pivote y en la sublista derecha todos los elementos mayores que el pivote. Supongamos que todos los elementos de la lista son distintos, aunque será preciso tener en cuenta los casos en que existan elementos idénticos.








        


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