Metodos de ordenamiento y busqueda

3501390-57594500-651510-52832000
UNIVERSIDAD AUTONOMA DE NUEVO LEON
FACULTAD DE INGENIERIA MECANICA Y ELECTRICA
Algoritmos Computacionales
Profesor del curso teorico: Sergio Ordoñez
Alumno:Erick Eduardo Vielma Martínez
Matricula: 1691586
Hora: N1
Método de ordenación de Shell
El ordenamiento Shell (Shell sort en inglés) es un algoritmo de ordenamiento. El método se denomina Shell enhonor de su inventor Donald Shell. Su implementación original, requiere O(n2) comparaciones e intercambios en el peor caso. Un cambio menor presentado en el libro de V. Pratt produce una implementacióncon un rendimiento de O(n log2 n) en el peor caso. Esto es mejor que las O(n2) comparaciones requeridas por algoritmos simples pero peor que el óptimo O(n log n). Aunque es fácil desarrollar unsentido intuitivo de cómo funciona este algoritmo, es muy difícil analizar su tiempo de ejecución.
El Shell sort es una generalización del ordenamiento por inserción, teniendo en cuenta dos observaciones:El ordenamiento por inserción es eficiente si la entrada está "casi ordenada".
El ordenamiento por inserción es ineficiente, en general, porque mueve los valores sólo una posición cada vez.
13 1494 33 82 25 59 94 65 23 45 27 73 25 39 10
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
Y se ordenan por comulnas10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45

Ordenamientoradixsort el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (porejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.
25 57 48 37 12 92 86 33
Asignamos los elementos encolas basadas en el dígito menos significativo de cada uno de ellos.
0:
1:
2:12 92
3:33
4:
5:25
6:86
7:57 37
8:48
9:
Después de la primera pasada, la ordenación queda:
12 92 33 25 86 57...