República Bolivariana De Venezuela Ministerio Del Poder Popular Para La Defensa

Universidad Nacional Experimental Politécnica De Las Fuerzas Armadas Unefa

Edo Mérida

Bucket sortIntegrantesJhoandry rujano ci 20940607jesennia sanchez ci19934333Eidy peña ci23727031Gleudys parra ci20573132

Método de ordenamientoBUCKET SORT

Es un algoritmo de ordenamiento que distribuye todos los elementos a ordenar entre un número finito de casilleros.

Mejor conocido como El ordenamiento por casilleros

EJEMPLO

29 4 10 9 30 7 17 22 21 5

4 ,9, 7, 5

10,17 29,22,21

30

Del 0-9

Del10-19

Del20-29

Del30

4579

1017

212229

30

4 5 7 9 10 17 21 22 29 30

también se puede decir que (BUSKET SORT) tiene Varias variantes o también conocido como algoritmo del cartero

es una variante del bucketsort utilizada cuando los elementos a ordenar disponen de varias claves y/o subclaves.

El nombre de este algoritmo viene del ejemplo de las oficinas postales; allí cuando hay que clasificar una carta para que llegue a su destino primero se clasifica según el país de destino, luego la ciudad o la región, después según la calle o el barrio de destino, etc. Es decir, este algoritmo utiliza varias claves para hacer ordenamientos sucesivos

• Se lleva a cabo completamente en memoria principal. Todos los objetos que se ordenan caben en la memoria principal de la computadora

Ordenamiento interno

• No cabe toda la información en memoria principal y es necesario ocupar memoria secundaria. El ordenamiento ocurre transfiriendo bloques de información a memoria principal en donde se ordena el bloque y este es regresado, ya ordenado, a memoria secundaria

Ordenamiento externo.

Tipos de ordenamiento

VENTAJAS:

Según reinosa “barbagallo” un ordenamiento se considera estable si mantiene el orden relativo que tenían originalmente los elementos con claves iguales. Si se tienen dos registros A y B con la misma clave en la cual A aparece primero que B, entonces el método se considera estable cuando A aparece primero que B en el archivo ordenado.

Es estable, cuando existen claves iguales se preserva el orden

existente.

Las claves son enteros, permite ordenar valores directos en un rango determinado. Este algoritmo es eficiente cuando la cantidad de casilleros es menor a la cantidad de claves.

El tiempo para clasificar los elementos es constante, las claves repetidas ingresan en un mismo casillero, no se hace comparaciones entre claves.

DESVENTAJAS:

El tiempo para clasificar los elementos en el peor de los casos es 0(n log n), usualmente esto no ocurre, sin embargo podría suceder.

El algoritmo no funciona de manera correcta cuando las claves son muy largas, como el tiempo de clasificación total es proporcional a la longitud de la clave y el número de elementos a ordenar.

No es eficiente cuando la cantidad de casilleros es mayor a la cantidad de claves, tampoco cuando el rango es desconocido. Por ejemplo si un arreglo (array en ingles) posee 800 enteros de cualquier valor este algoritmo no trabajara de manera eficiente.

Estos algoritmos necesitan una gran cantidad d memoria extra, en ocasiones se requiere memoria extra, los algoritmos “in situ” son los que necesitan memoria extra pequeña y constante, al contrario de estos que no son “in situ”, cuando transforman las estructuras de datos necesita gran cantidad de memoria extra.

El algoritmo contiene los siguientes pasos:1. Crear una colección de casilleros vacíos

2. Colocar cada elemento a ordenar en un único casillero

3. Ordenar individualmente cada casillero

4. Devolver los elementos de cada casillero concatenados por orden

3 9 21 25 29 37 43 49

EXPLICACIÓN DE FUNCIONAMIENTO

1) Se tiene que tener

previamente los datos que se van a ordenar en un

vector

2) Se codifican los casilleros que se desean utilizar y sus intervalos

3) Se establecen los condiciones o reglas que deben

cumplir cada valor para estar

en un determinado

casillero

4) Se ordena cada casillero por separado.

5) Se asignan nuevamente los valores

al vector original

Algoritmo de Bucket Sort

PSEUDOCÓDIGO

Aquí elementos es el vector a ordenar y n el número de casilleros que queremos usar. Para buscar el casillero adecuado para asignar un valor se puede utilizar la técnica que más convenga, según cómo queramos ordenar los datos.