sorting

Arturo Díaz Pérez

Análisis y Complejidad de Algoritmos

Métodos de Ordenamiento
Arturo Díaz Pérez
¬
®
¯
°
±
²

Tipos de ordenamiento y medidas de eficiencia
Algoritmos básicosQuickSort
HeapSort
BinSort
RadixSort
Arboles de Decisión

Análisis y Diseño de Algoritmos

Sorting-1

Tipos de Ordenamiento
F Ordenamiento interno.
ß Se lleva a cabo completamente en memoriaprincipal. Todos los
objetos que se ordenan caben en la memoria principal de la
computadora

F Ordenamiento externo.
ß No cabe toda la información en memoria principal y es necesario
ocupar memoriasecundaria. 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

Análisis y Diseñode Algoritmos

Análisis y Complejidad de Algoritmos

Sorting-2

1

Arturo Díaz Pérez

Formulación

ß Registros:
ß Llaves:
ß Obtener la secuencia
ß tal que,

r1, r2, ..., rn
k1, k2,..., kn

ri1 , ri2 ,..., rin
ki1 ≤ ki2 ≤ ... ≤ kin

Análisis y Diseño de Algoritmos

Sorting-3

Criterios de Eficiencia
F Criterios de eficiencia
ß El número de pasos
ß El número decomparaciones entre llaves para ordenar n
registros.
/De utilidad cuando la comparación entre llaves es costosa
ß El número de movimientos de registros que se requieren para
ordenar n registros.
/Deutilidad cuando el movimiento de registros es costoso

Análisis y Diseño de Algoritmos

Análisis y Complejidad de Algoritmos

Sorting-4

2

Arturo Díaz Pérez

Métodos Simples deOrdenamiento
F Métodos simples
ß Método de Burbujeo
ß Método de Inserción
ß Método de Selección

Sorting-5

Análisis y Diseño de Algoritmos

Método de Burbujeo
25

3

12

19

2

1

9

61

25

3

12

19

2

6

9

2

25

3

12 19

6

9

3

25

6

12

19

9

6

25

9

12 19

9

25

12 19

12

25 19

void Burbujeo( int A[],...