Ingeniando una función de ordenamiento

PONTIFICIA UNIVERSIDAD CATÓLICA MADRE & MAESTRA

Facultad de Ciencias de La Ingeniería Departamento de Ingeniería de Sistemas y Computación

ESTRUCTURA DE DATOS & ALGORITMOS Prof. Roberto Carlos Abreu Díaz
ST-ISC-423-T-002

“Ingeniando Una Función de Ordenamiento”
JON L. BENTLEY || M. DOUGLAS McILROY

Tema:

[Informe]

Joel Aneudi Reyes Borbón
2007-0072

Elaborado por:Santiago de los Caballeros, R.D. 15/Nov/2010.-

“Ingeniando Una Función de Ordenamiento” [Informe] ____________________________________________________________

__________________

Contenido:
Introducción La Interfaz qsort Un Simple qsort Un Modelo de Costos Eligiendo un Elemento de Partición Una Prueba de Tiempo La Oportunidad de Elementos Iguales Otras Mejoras Certificación de RendimientoComparando Clases Conclusión ……………………………………….. 3 ……………………………………….. 4 ……………………………………….. 6 ……………………………………….. 7 ……………………………………….. 10 ……………………………………….. 11 ……………………………………….. 12 ……………………………………….. 14 ……………………………………….. 15 ……………………………………….. 16 ……………………………………….. 18

Bibliografía:  Engineering a Sort Function.pdf  http://www.worldlingo.com/ma/enwiki/es/Quicksort

2

“Ingeniando Una Función deOrdenamiento” [Informe] ____________________________________________________________

__________________

Introducción
La edición estándar de Quicksort y otras variantes preservan el problema de haber utilizado almacenamiento estático en la ejecución de sus funciones por lo que resultan defectuosas al ser llamadas de forma recursiva dentro de una función de comparación o al implementarse en lacomputación multiprocesos. Este informe está orientado a presentar con detalles la evolución o historial de pasos que surgieron en búsqueda de construir un nuevo algoritmo para Quicksort, el cual evite la desaceleración extrema que ocurre al utilizar entradas razonables, sea lo suficientemente rápido al manejar entradas aleatorias y maneje de manera eficiente el espacio de datos y código, manteniendo suestabilidad.

3

“Ingeniando Una Función de Ordenamiento” [Informe] ____________________________________________________________

__________________

La Interfaz qsort
Utilizando como punto de partida la función iisort, la cual ordena n enteros dentro de un arreglo a. El algoritmo varía el índice i desde la segunda posición hasta la posición del último elemento y varía j para rotar eli-ésimo elemento hacia la izquierda hasta lograr un lugar adecuado dentro del subarreglo anterior.

La función iswap (i, j, a) intercambia los enteros a[i] y a[j]. Este algoritmo de ordenamiento se le conoce como Insertion Sort, por ende la primera i en la función iisort hace referencia a Integer (entero) y la segunda i representa Insertion (inserción). El mismo utiliza alrededor de n2/4 comparacionesen un arreglo permutado aleatoriamente, y nunca utiliza más de n2/2 comparaciones. Basándonos en la interfaz general de qsort tenemos:

void qsort (char *a, int n, int es, int *cmp());
Como primer parámetro recibe un puntero hacia el arreglo que será ordenado. Los siguientes dos parámetros indican el número de elementos y el tamaño en bytes de cada uno. El último parámetro es un puntero a unafunción de comparación que a su vez recibe dos punteros a argumentos. Esta retorna un entero menor, igual o mayor que cero cuando el primer puntero señala un argumento con valor menor, igual o mayor que el segundo, respectivamente. A continuación se muestra una típica función de comparación y un ejemplo de llamada a la función qsort para ordenar un arreglo de enteros no-negativos.

4“Ingeniando Una Función de Ordenamiento” [Informe] ____________________________________________________________

__________________

Para ordenar un arreglo de Strings de len-byte terminadas en caracteres nulos utilizamos la rutina estándar para comparar Strings, strcmp:

qsort (a, n, len, strcmp)
En el caso de ordenar un arreglo de punteros a Strings, usamos strcmp con un pequeño nivel de...