| Pregunta: | 14303 - ORDENAMIENTO QUICK SORT EN FICHEROS DE ACCESO ALEATORIO |
| Autor: | Gerson J. Oviedo Rojas |
| Necesito bastante informacion del metodo de ordenamiento Quick Sort en ficheros de acceso aleatorio. Por favor si conoce alguna direccion en internet favor hacermela saber. Gracias por su colaboracion. | |
| Respuesta: | Luis Machuca B |
| Gerson: El método de ordenamiento Quicksort es un método de combinación recursiva que permite aprovechar una buena rlación cantidad_datos_a_ordenar/velocidad_permutación aún para una gran cantidad de datos, tal es así que estadísticamente se puede decir que le toma el mismo trabajo ordenar 10000 elemetos que 5000000. El algoritmo para este método consta en cuatro pasos eseciales: 1.- Seleccionar un área de ordenación 2.- Seleccionar, dentro de esta área, un PIVOTE cualquiera 3.- Reparticionar el área de modo que el pivote quede bicado adecuadamente, y los elementos menores qu él en el área, queden antes de él (no necesariamente ordenados) 4.- Partir el área en dos subáreas separadas por el pivote y repasar cada área con el paso 1. LA compleejidad esta en lso pasos 1 y 3 que son los más complicados. Usualmente el pivote se escoge al azar pero una forma buena deescogerlo es el mínimo o máximo entre los tres elementos del inicio, medio y final. Si llamamos A y B a los límites del área de ordenación, N al número de elementos del archivo, Z a la posción de un elemento determinado dentro del archivo (usado para el paso 3), y K al pivote, entonces se puede proceder como sigue: QuickSort(FILE, A, B, N): { if A=B then END QuickSort: K = (pivote al azar); Particionar(FILE,A,B,K,Z); QuickSort(FILE, A, Z-1, N); QuickSort(FILE, Z, B, N); } El método Particionar es ajeno al QuickSort y cada uno lo hace como quiere, pero el que yo uso, opera de la siguiente forma: 1º Tomamos el pivote y dejamos su posición en Z 2º Contamos cuántos elementos menores que K hay en el FILE entre A y B (B no inclusive) 3º Intercambiamos el pivote con el elemento ubicado en esa psición. 4º Desde el elemento en la posición Z,tomamos cada mayor que K hacia atrás y cada menor que K hacia adelante, y los intercambiamos 5º Colocamos Z como la nueva posición del pivote. Aquí aseguramos que los elementos A hasta Z son todos menores o iguales que el pivote, lo cual reduce a la mitad el tiempo de ordenación de esa subsección. Actualizamos A y B con los valores márgen de esta subsección Retornamos Z El código de esto es bastante variable en cuanto a que opera diferente teniendo encuenta si los datos del archivo van de 0 a N-1, o de 1 a N, además de que depende del método de intercambio que puede resultar muy lento para la ordenación. En general, es algo complicado colocarlo en un archivo aleatorio, algunos dicen que no se puede pero yo creo que sí, no debiera ser mucho problema pero se va a gastar mucha memoria... Lo mejor es que nos contactemos por correo, dentro de dos o tres días te enviaré mi modelo del QuickSort y del Particionar para C/C++ (adaptable a Visualcon pequeñas modificaiones) y después podremos revisar cómo trabaja. Te contacto por correo en unos días. Suerte: Luis | |