; SORTSCRN.ACT - Form two identical›;   windows on mode 7 screen with›;   random data.  Then, sort the›;   left-hand window using QuickSort,›;   and the righ-hand window using›;   BubbleSort.  In order to do this›;   simultaneously, we will employ›;   the multitasking routines in›;   FORK.ACT.››; by Mark Rose›; this version: 4/25/85››INCLUDE "FORK.ACT"›››    ›; NOTES:  Both of the sorting methods›;   are not written to be as efficient›;   as possible.  In particular, both›;   sorts can be made faster by taking›;   out the calls to compare and swap›;   routines, and inserting in-line›;   code, instead.  In this demo,›;   however, I have chosen clarity›;   over efficiency since the ›;   superiority of QuickSort is still›;   quite apparent.››››; Define the number of rows and›; columns on the two screen areas›; to be sorted.›; Also, SortSize = NRows*NCols›; and RightCol is the offset in bytes›; of the right-hand screen window›; from the left edge of the screen.››DEFINE NCols    = "19",›       NRows    = "80",›       SortSize = "1520",›       RightCol = "21"››; Arrays of pointers to screen data›; for QuickSort (QData) and BubbleSort›; (BData), respectively.››CARD ARRAY BData( SortSize ),›           QData( SortSize )››››; MakeArray - form the list of pointers›;   to screen memory.››PROC MakeArray()›    CARD row, col, index,›         screen = $58›    BYTE POINTER qAddr, bAddr›    BYTE c››    index = 0›    FOR col = 0 TO NCols-1›      DO›        qAddr = screen + col›        bAddr = qAddr + RightCol›        FOR row = 0 TO NRows-1›          DO›            c = Rand( 255 )›            qAddr^ = c›            bAddr^ = c›            QData( index ) = qAddr›            BData( index ) = bAddr›            qAddr ==+ 40›            bAddr ==+ 40›            index ==+ 1›          OD›      OD›  ; At this point, index shoul equal›  ; SortSize.  In the spirit of a›  ; simplistic demo, however, no›  ; check will be performed.›RETURN››››;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;›;›; Bubble sort routines:›;›;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;››; BCompare - Compare two bytes.››BYTE FUNC BCompare( CARD i, j )›    BYTE POINTER p1, p2››    p1 = BData( i )›    p2 = BData( j )›    IF p1^ < p2^ THEN›        RETURN( 1 )›    FI›RETURN( 0 )››››; BSwap - Interchange two sort›;   elements.››PROC BSwap( CARD i, j )›    BYTE POINTER p1, p2›    CARD temp››    p1 = BData( i )›    p2 = BData( j )›    temp = p1^›    p1^ = p2^›    p2^ = temp›RETURN››››; Bubble - Sort list by bubble sort›;   algorithm.  Use BSwap to inter-›;   change out-of-order elements.››PROC Bubble()›    INT passes,›        index›    BYTE POINTER p1,›                 p2››    FOR passes = 0 TO SortSize-2›      DO›        index = SortSize-1›        WHILE index>passes›          DO›            IF BCompare( index, index-1 ) THEN›                BSwap( index-1, index )›            FI›            index ==- 1›          OD›      OD›RETURN››››;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;›;›; QuickSort routines:›;›;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;››MODULE››CARD ListSize››CARD ARRAY List( 64 ) ; Big enough for 64K sort elements››››; QCompare - Compare two bytes.››BYTE FUNC QCompare( CARD i, j )›    BYTE POINTER p1, p2››    p1 = QData( i )›    p2 = QData( j )›    IF p1^ < p2^ THEN›        RETURN( 1 )›    FI›RETURN( 0 )››››; QSwap - Interchange two sort›;   elements.››PROC QSwap( CARD i, j )›    BYTE POINTER p1, p2›    CARD temp››    p1 = QData( i )›    p2 = QData( j )›    temp = p1^›    p1^ = p2^›    p2^ = temp›RETURN››››; AddList - Add a partition to the list››PROC AddList( CARD low, high )›    IF high+1 > low+1 THEN›        List( ListSize ) = low›        ListSize ==+ 1›       List( ListSize ) = high›        ListSize ==+ 1›    FI›RETURN››››; GetFirst - Retrieve last low,high›;   pair from list of partitions.››PROC GetFirst( CARD POINTER lowP, highP )›    ListSize ==- 1›    highP^ = List( ListSize )›    ListSize ==- 1›    lowP^  = List( ListSize )›RETURN›  ›››; Partition - Divide sort array into›;   two partitions.››CARD FUNC Partition( CARD low, high )›    CARD i, j, pivot, mid››  ; Find median of 1st,middle,and last›  ; elements to use as pivot for partitioning.›    mid = (low+high) RSH 1›    IF QCompare( mid, low ) THEN›        QSwap( low, mid )›    FI›    IF QCompare( high, low ) THEN›        QSwap( low, high )›    FI›    IF QCompare( mid, high ) THEN›        QSwap( mid, high )›    FI››  ; Found pivot, now partition array.›    pivot = high›    i = low›    j = high›    WHILE i < j›      DO›        WHILE QCompare( i, pivot )›          DO›            i ==+ 1›          OD›        WHILE (QCompare(j,pivot)=0) AND (j>i)›          DO›            j ==- 1›          OD›        IF i < j THEN›            QSwap( i, j )›        FI›      OD›    QSwap( i, high )›RETURN( i )››››; Quick - Sort using the QuickSort›;   algorithm.››PROC Quick()›    CARD low, middle, high, i››    ListSize = 0›    AddList( 0, SortSize-1 )›    WHILE ListSize > 0›      DO›        GetFirst( @low, @high )›        middle = Partition( low, high )›      ; Put larger partition onto stack first›      ; in order to decrease maximum stack size.›        IF (middle-low) > (high-middle) THEN›            AddList( low, middle-1 )›            AddList( middle+1, high )›        ELSE›            AddList( middle+1, high )›            AddList( low, middle-1 )›        FI›      OD›RETURN››››;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;›;›; Main routine - Calls Quick and›;   Bubble to sort both halves of›;   screen.›;›;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;››PROC Main()›    DEFINE startKey = "1"›    BYTE console = $D01F››  ; Set up graphics data to sort.›    Graphics( 7 )›    MakeArray()›    Print( "   QuickSort       " )›    PrintE( "    BubbleSort" )››  ; Start quicksort as background›  ; process with fore- and background›  ; time slices of 1 jiffy›    TimeSlice( 0 ) = 1›    TimeSlice( 1 ) = 1›    Fork( Quick )››  ; Start bubble sorting.›    Bubble()›    PrintE("Finished - press  START ")››  ; Now loop until START key pressed.›    WHILE console & startKey›      DO›      OD›    Graphics( 0 )›RETURN›