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 particular del método de ordenación por urnas (binsort). Este método utiliza urnas, cada urna contiene todos los registros con una misma clave.

El proceso consiste en examinar cada registro r a clasificar y situarle en la urna i, coincidiendo i con el valor del campo clave de r. En la mayoría de los casos en que se utilice el algoritmo, será necesario guardar más de un registro en una misma urna por tener claves repetidas. Entonces estas urnas hay que concatenarlas en el orden de menor índice de urna a mayor, así quedará el array en orden creciente respecto al campo clave.



Comentarios

Publicar un comentario

Entradas más populares de este blog

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