Por favor, use este identificador para citar o enlazar este ítem:
https://hdl.handle.net/20.500.12008/3505
Cómo citar
Título: | Adaptative sampling strategies for Quickselect |
Autor: | Martínez, Conrado Panario, Daniel Viola, Alfredo |
Tipo: | Reporte técnico |
Fecha de publicación: | 2004 |
Resumen: | Quickselect con median-of-3 es usado ampliamente en la práctica y su comportamiento bastante bien comprendido. Sin embargo, la siguiente variante adaptativa, que llamamos proportion-from-3, no ha sido analizada previamente: "elegir como pivot el elemento más pequeño de la muestra si el rango relativo del elemento buscado está por abajo de 1/3; elegir el más grande si el rango relativo está por encima de 2/3; y elegir el mediano si el rango relativo está entre 1/3 y 2/3". Analizamos primero el número promedio de comparaciones realizadas al usar proportion-from-2 y luego al usar proportion-from-3. También analizamos nu-find, una generalización de proportion-from-3 con extremos de intervalo en los valores nu y 1-nu. Mostramos que existe un valor óptimo de nu y damos el rango de valores de nu en los que la estrategia nu-find supera a median-of-3. Luego, consideramos el costo total promedio de estas estrategias, teniendo en cuenta tanto el costo de las comparaciones como de los intercambios. Nuestros resultados apuntan fuertemente a que una implementación apropiada de nu-find podría ser el método preferible en un entorno práctico. También estudiamos el comportamiento de proportion-from-s con s ] 3 y en particular mostramos que estrategias del estilo proportion-from-s son óptimas cuando s tiende a infinito. |
Editorial: | UR. FI – INCO. |
Serie o colección: | Reportes Técnicos 04-14 |
Citación: | MARTÍNEZ, C., PANARIO, D., VIOLA, A. "Adaptative sampling strategies for Quickselect". Reportes Técnicos 04-14. UR. FI – INCO, 2004. |
ISSN: | 0797-6410 |
Licencia: | Licencia Creative Commons Atribución – No Comercial – Sin Derivadas (CC BY-NC-ND 4.0) |
Aparece en las colecciones: | Reportes Técnicos - Instituto de Computación |
Ficheros en este ítem:
Fichero | Descripción | Tamaño | Formato | ||
---|---|---|---|---|---|
TR0414.pdf | 849,15 kB | Adobe PDF | Visualizar/Abrir |
Este ítem está sujeto a una licencia Creative Commons Licencia Creative Commons