* Problem - Sort array of full word integers using fastest exec method * Date - 12/21/07 * Author - Rafa Pereira * Ref. - z390 Mainframe Assembler Coding Contest on www.z390.org * * It is an implementation of the QuickSort Algorithm. * This particular implementation is based on the code available at: * http://www.mycsresource.net/articles/programming/sorting_algos/ * quicksort/ * An interesting and clear explanation of the algorithm is also * available at the same URL. * * I have transformed it into an iterative implementation following the * guidance at * http://www.geocities.com/siliconvalley/garage/3323/aat/a_recu.html * * So, the code used as the starting point is: * * public void quickSortIterative(int start, int end) * { * int i; * int k; * push (start, end); * * while (pop(s,e) OK) //i.e. while stack is not empty * { * if (e - s >= 1) * { * int pivot = array[s]; * -> I will change this to pivot=array[(s+e)/2] * * i = s; * k = e; * * while (k > i) * { * while (array[i] <= pivot && i <= e && k > i) i++; * while (array[k] > pivot && k >= s && k >= i) k--; * if (k > i) swap(i, k); * } * * swap(s, k); * push(s, k - 1); * push(k + 1, e); * } * } * return; * } * * Changes from P4RAFA1: * Routines are now included in-stream, without BAL/BR instructions. * Register usage redesigned to reduce inter-register data movement. * Other minor changes. ********************************************************************** * 12/23/07 DSH1 Don Higgins change F8 to F08, remove RUNSYS=MVS ********************************************************************** * REGISTERS * --------- * * R0 WORK * R1 I, WORK * R2 K * R3 S, START * R4 E, END * R5 WORK * R6 * R7 PIVOT * R8 BASE ADDRESS OF ARRAY TO SORT * R9 STACK POINTER * R10 STACK BASE ADDRESS * R11 * R12 * R13 BASE ADDRESSING REGISTER * R14 * R15 ********************************************************************** * P4RAFA2 ZMFACC CODE,START,NAME='RAFA' * ********************************************************************** * INIT ROUTINE - ROUTINE FOR INITIALIZATIONS * * R3: ZERO * R4: OFFSET OF LAST ELEMENT IN THE ARRAY TO SORT * R8: BASE ADDRESS OF THE ARRAY TO SORT * R9: ZERO * R10: BASE ADDRESS OF THE STACK ********************************************************************** INIT SR R3,R3 R3 := 0 L R4,TABSIZM4 R4 := OFFSET LAST ELEMENT LA R8,TABLE R8 -> ARRAY TO SORT SR R9,R9 R9 := 0 LA R10,STACK R10 -> STACK ********************************************************************** * INIT ROUTINE - END ********************************************************************** * ********************************************************************** * QUICK-SORT ROUTINE - ITERATIVE. * SELECTS A PIVOT ELEMENT. * PARTITIONS THE INPUT ARRAY INTO TWO ARRAYS, * ONE WITH ELEMENTS LESS-THAN-OR-EQUAL-TO THE * PIVOT AND ONE WITH ELEMENTS GREATER-THAN THE * PIVOT. * PROCESSES EACH OF THE TWO SUBARRAYS. * THE PARTITIONING IS DONE IN-PLACE. * * ON ENTRY: * R3: INDEX IN THE DATA ARRAY OF THE LEFTMOST ELEMENT * R4: INDEX IN THE DATA ARRAY OF THE RIGHTMOST ELEMENT * R8: BASE ADDRESS OF THE ARRAY TO SORT * * ON RETURN: * R3: MODIFIED * R4: MODIFIED * * public void quickSortIterative(int start, int end) * { * int i; * int k; * push (start, end); * * while (pop(s,e) OK) //i.e. while stack is not empty * { * if (e - s >= 1) * { * int pivot = array[s]; * -> I will change this to pivot=array[(s+e)/2]: * * swap(s, (s+e)/2); * pivot = array[s]; * * i = s; * k = e; * * while (k > i) * { * while (array[i] <= pivot && i <= e && k > i) i++; * while (array[k] > pivot && k >= s && k >= i) k--; * if (k > i) swap(i, k); * } * * swap(s, k); * push(s, k - 1); * push(k + 1, e); * } * } * return; * } ********************************************************************** QSORT B QSORT03 BYPASS INITIAL PUSH+POP PAIR * * BEGINNING OF WHILE (POP(S,E) OK) LOOP * ********************************************************************** * POP (S,E) * * S IS LOADED INTO R3 * E IS LOADED INTO R4 ********************************************************************** POP LTR R9,R9 STACK IS ALREADY EMPTY? BZ QSORTZ YES: END WITH STACK-EMPTY * S R9,F08 UPDATE R9 (STACK POINTER) L R3,0(R9,R10) POP R3 FROM STACK L R4,4(R9,R10) POP R4 FROM STACK ********************************************************************** * POP ROUTINE - END ********************************************************************** * * BEGINNING OF IF (E - S >= 1) FRAGMENT * QSORT03 LR R5,R4 R5 := E SR R5,R3 R5 := E - S C R5,F04 R5 < 4? (4 BECAUSE FULLWORD SIZE) BL POP YES: BACK TO WHILE LOOP * SRA R5,1 R5 := (E-S)/2 AR R5,R3 R5 := (E-S)/2 + S = (E+S)/2 N R5,FFFFFFFC ROUND TO MULTIPLE OF 4 L R7,0(R5,R8) PIVOT (R7) := ARRAY[(S+E)/2] * L R1,0(R3,R8) SWAP ... ST R1,0(R5,R8) ... (E+S)/2 ... ST R7,0(R3,R8) ... AND S * LR R1,R3 I := S LR R2,R4 K := E * * BEGINNING OF WHILE (K > I) LOOP * QSORTWH2 CR R1,R2 I < K? BNL QSORT01 NO: END OF WHILE (K>I) * * BEGINNING OF WHILE (ARRAY[I] ...) LOOP * QSORTWH3 C R7,0(R1,R8) PIVOT < ARRAY[I]? BL QSORTWH4 YES: END OF WHILE (ARRAY[I]..) CR R1,R2 I < K? BNL QSORTWH4 NO: END OF WHILE (ARRAY[I]..) CR R4,R1 E < I? BL QSORTWH4 YES: END OF WHILE (ARRAY[I]..) LA R1,4(R1) I++ (4 BECAUSE FULLWORD SIZE) B QSORTWH3 BACK TO WHILE (ARRAY[I]..) LOOP * * BEGINNING OF WHILE (ARRAY[K] ...) LOOP * QSORTWH4 C R7,0(R2,R8) PIVOT < ARRAY[K]? BNL QSORT02 NO: END OF WHILE (ARRAY[K]..) CR R2,R1 K < I? BL QSORT02 YES: END OF WHILE (ARRAY[K]..) CR R2,R3 K < S? BL QSORT02 YES: END OF WHILE (ARRAY[K]..) S R2,F04 K-- (4 BECAUSE FULLWORD SIZE) B QSORTWH4 BACK TO WHILE (ARRAY[K]..) LOOP * * END OF WHILE (ARRAY[K] ...) LOOP * QSORT02 CR R1,R2 I < K? BNL QSORT01 NO: END OF WHILE (K>I) LOOP * L R0,0(R1,R8) SWAP ... L R5,0(R2,R8) ... I ... ST R0,0(R2,R8) ... AND ... ST R5,0(R1,R8) ... K * B QSORTWH2 BACK TO WHILE (K>I) LOOP * * END OF WHILE (K > I) LOOP * QSORT01 L R0,0(R3,R8) SWAP ... L R5,0(R2,R8) ... S ... ST R0,0(R2,R8) ... AND ... ST R5,0(R3,R8) ... K * S R2,F04 R2:=K-1 (4 BECAUSE FULLWORD SIZE) * ********************************************************************** * PUSH (S,K-1) * PUSH (K+1,E) * * NOTE: STACK-FULL CONDITION IS NOT CHECKED. STACK MUST BE PROPERLY * DIMENSIONED. * * S IS IN R3 * K-1 IS IN R2 * E IS IN R4 ********************************************************************** PUSH02 ST R3,0(R9,R10) PUSH R3 INTO STACK (S) ST R2,4(R9,R10) PUSH R2 INTO STACK (K-1) LA R2,8(R2) R2:=K+1 (8 BECAUSE FULLWORD SIZE) ST R2,8(R9,R10) PUSH R2 INTO STACK (K+1) ST R4,12(R9,R10) PUSH R4 INTO STACK (E) LA R9,16(R9) UDATE STACK POINTER ********************************************************************** * PUSH ROUTINE - END ********************************************************************** * B POP BACK TO WHILE (POP(S,E) OK) LOOP * QSORTZ EQU * * ********************************************************************** * QUICK-SORT ROUTINE - END ********************************************************************** * ZMFACC CODE,END * ********************************************************************** * DATA ********************************************************************** TABSIZM4 DC A(TABLEEND-TABLE-4) TABLE SIZE MINUS 4 F04 DC F'4' CONSTANT 4 (F4 IS USED BY MACRO ZMFACC) F08 DC F'8' CONSTANT 8 (F8 IS USED BY MACRO ZMFACC) FFFFFFFC DC X'FFFFFFFC' TWO LOW ORDER BITS = 00 STACK DS 50F STACK ZMFACC INPUT,START ZMFACC OUTPUT,START TABLE DC 20A(TABLEEND-*) TABLEEND EQU * ZMFACC INPUT,END ZMFACC OUTPUT,END * END