IDENTIFICATION DIVISION. PROGRAM-ID. QUICKSRT. * * Módulo que clasifica la tabla de nombre TABLA-A-CLASIFICAR, * por CLAVE (en este ejemplo, sus cinco primeras posiciones). * En la variable NUM-ELEMENTOS debe estar el numero real de * elementos que contiene la tabla a clasificar. Debe ser * mayor que cero; si puede tener un valor cero, hay que preguntar * si esto es así para terminar inmediatamente el proceso. * DATA DIVISION. WORKING-STORAGE SECTION. 01 CLAVE-MEDIO PIC X(5). * 01 ELEM-INTERCAMBIO PIC X(10). * 01 INI-WORK PIC 9(8) COMP. 01 FIN-WORK PIC 9(8) COMP. 01 MEDIO PIC 9(8) COMP. * **** PILA (para resolver la recursividad de "PARTICION"). 01 STACK-RECURSIVIDAD. 05 ELEM-STACK OCCURS 100 INDEXED BY IND-STACK. 10 INISTACK INDEX. 10 FINSTACK INDEX. **** LINKAGE SECTION. 01 NUM-ELEMENTOS PIC 9(8) COMP. * 01 TABLA-A-CLASIFICAR. 05 ELEMENTO OCCURS 10000, INDEXED BY INICIAL-P, FINAL-P, INI, FIN, IND-WORK. 10 CLAVE PIC X(5). 10 FILLER PIC X(5). *************************************************** * PROCEDURE DIVISION USING NUM-ELEMENTOS, TABLA-A-CLASIFICAR. MAIN SECTION. COMIENZO. * Inicialización de la Pila de Recusividad y de los índices * de la tabla a clasificar. * SET INICIAL-P TO 1. SET FINAL-P TO NUM-ELEMENTOS. SET IND-STACK TO 2. SET INISTACK (2) TO INICIAL-P SET FINSTACK (2) TO FINAL-P. * * Proceso principal recursivo de QUICKSORT. * PERFORM PROCESAR-PARTICION UNTIL IND-STACK LESS 2. * EXIT PROGRAM. * * PROCESAR-PARTICION. * Recuperación de la Cabeza de la Pila, con datos de la llamada * recursiva: índices Inicial y Final de la particion a tratar, * y llamada a PARTICION para dividirla en dos subconjuntos. * * Descabezar la Pila y comprobar los dos Subconjuntos: * Claves Menores o Iguales que el Pivote: (INI <--> FINAL-P); * Claves Mayores o Iguales que el Pivote: (INICIAL-P <--> FIN). * * Si un Subconjunto tiene menos de dos elementos, ya está * ordenado; si tiene dos, se comprueba si están ya en orden, y * se intercambian si es preciso; en otro caso, se insertan sus * datos en la Pila para próximas llamadas recursivas. * SET INICIAL-P TO INISTACK (IND-STACK). SET FINAL-P TO FINSTACK (IND-STACK). * PERFORM PARTICION. * SET IND-STACK DOWN BY 1. * * SUBCONJUNTO 1: Delimitado por INI Y FINAL-P. * SET IND-WORK TO INI SET IND-WORK UP BY 1 IF FINAL-P GREATER IND-WORK SET IND-STACK UP BY 1 SET INISTACK (IND-STACK) TO INI SET FINSTACK (IND-STACK) TO FINAL-P ELSE IF FINAL-P EQUAL IND-WORK AND CLAVE (INI) GREATER CLAVE (FINAL-P) MOVE ELEMENTO (INI) TO ELEM-INTERCAMBIO MOVE ELEMENTO (FINAL-P) TO ELEMENTO (INI) MOVE ELEM-INTERCAMBIO TO ELEMENTO (FINAL-P). * * SUBCONJUNTO 2: Delimitado por INICIAL-P Y FIN. * SET IND-WORK TO INICIAL-P SET IND-WORK UP BY 1 IF FIN GREATER IND-WORK SET IND-STACK UP BY 1 SET INISTACK (IND-STACK) TO INICIAL-P SET FINSTACK (IND-STACK) TO FIN ELSE IF FIN EQUAL IND-WORK AND CLAVE (INICIAL-P) GREATER CLAVE (FIN) MOVE ELEMENTO (INICIAL-P) TO ELEM-INTERCAMBIO MOVE ELEMENTO (FIN) TO ELEMENTO (INICIAL-P) MOVE ELEM-INTERCAMBIO TO ELEMENTO (FIN). * ************************************************************ * Proceso de Partición del Subconjunto (INICIAL-P <--> FINAL-P). * Se selecciona el Pivote (el elemento central), y se * almacena su CLAVE en CLAVE-MEDIO. * PARTICION SECTION. PROCESO. SET INI TO INICIAL-P. SET FIN TO FINAL-P. * SET INI-WORK TO INI SET FIN-WORK TO FIN COMPUTE MEDIO = (INI-WORK + FIN-WORK) / 2. MOVE CLAVE (MEDIO) TO CLAVE-MEDIO. * PERFORM INTERCAMBIAR-ELEMS UNTIL INI GREATER FIN. * GO TO FINAL-PARTICION. * * INTERCAMBIAR-ELEMS. * Intercambio de elementos. Simultáneamente por el principio y * por el final del Subconjunto; cada vez que se encuentran dos * elementos descolocados, se intercambian, hasta que los dos * índices de intercambio (INI y FIN) se cruzan. * * 1) Búsqueda de un elemento descolocado en el principio del * Subconjunto (cuando su CLAVE es mayor o igual que CLAVE-MEDIO). * 2) Búsqueda de un elemento descolocado en el final del * Subconjunto (cuando su CLAVE es menor o igual que CLAVE-MEDIO). * 3) Intercambio de ambos elementos (excepto si los índices INI * y FIN se han cruzado ya, en cuyo caso se ha terminado). * PERFORM VARYING INI FROM INI BY 1 UNTIL CLAVE (INI) NOT LESS CLAVE-MEDIO END-PERFORM. * PERFORM VARYING FIN FROM FIN BY -1 UNTIL CLAVE (FIN) NOT GREATER CLAVE-MEDIO END-PERFORM. * IF INI NOT GREATER FIN MOVE ELEMENTO (INI) TO ELEM-INTERCAMBIO MOVE ELEMENTO (FIN) TO ELEMENTO (INI) MOVE ELEM-INTERCAMBIO TO ELEMENTO (FIN) SET INI UP BY 1 SET FIN DOWN BY 1. * FINAL-PARTICION. EXIT.