[futurebasic] Re: [FB] QuickSort Progress

Message: < previous - next > : Reply : Subscribe : Cleanse
Home   : December 1998 : Group Archive : Group : All Groups

From: Jay Reeve <jktr@...>
Date: Sat, 12 Dec 98 00:57:08 -0600
Mark,

I'm sure I don't understand it any better than you, but I would think you 
could do something with your split&. Check to see how many times it will 
be divided by 2 and make that your indicator.

I don't see where split& is initialized in your FN, but I presume it 
should be set to numRecs&/2. At that point you could call this FN:

CLEAR LOCAL FN howManySplits(split&)
  DIM count%
  WHILE split& > 1
    INC count%
    split& = split& >> 1
  WEND
END FN = count%

Then each time you reach split& = split& / 2 (BTW, >> is faster), 
decrease count% to know how many are left.

This doesn't pertain to your question, but your sort routine looks to me 
like a perfect candidate for XREF@ arrays. It seems to me they would sure 
make your code easier to understand and work with. After your code below, 
I've appended a version using XREF@ you could try if you're interested. 
If you do, I'd like to learn how the speed compares with what you're 
doing now. Double check, but I believe I got it to do the same thing 
yours did. 

 0"0
 =J= a  y
  "

>I don't understand the QuickSort Routine very well, but I want to put a
>progress indicator on the screen while I'm sorting. Is it possible to tell
>where you are in a quicksort? How would one go about it?
>
>Here's the routine I'm using:
>
>LOCAL FN QuickSort(dataHndl&,numRecs&,recSize,beginChar,strLen)
>  DIM indexHndl&
>  DIM i&,split&,testElem&,thisElem&,elemNum&,otherElem&,whichPos&,temp&
>  DIM recSize,strLen
>  DIM test$,target$
>
>  CURSOR _watchCursor
>  indexHndl&=FN NEWHANDLE((numRecs&)*4)
>
>  DEC(numRecs&)                            'shift to zero based array
>
>  LONG IF indexHndl&
>
>    FOR i&=0 TO numRecs&                  'create index
>      POKE LONG [indexHndl&]+(i&*4),i&
>    NEXT
>
     split& = numRecs& >> 1
     count  = FN howManySplits(split&)

>    WHILE split& <> 0
>      elemNum& = numRecs& - split&
>
>      FOR thisElem& = 0 TO elemNum&
>        testElem& = thisElem&
>
>      DO
>      otherElem& = testElem& + split&
>
>      whichPos&=PEEK LONG([indexHndl&]+((testElem&)*4))'
>      BLOCKMOVE [dataHndl&]+(whichPos&*recSize)+beginChar,@test$+1,strLen
>      POKE @test$,strLen
>
>      whichPos&=PEEK LONG([indexHndl&]+((otherElem&)*4))'
>      BLOCKMOVE [dataHndl&]+(whichPos&*recSize)+beginChar,@target$+1,strLen
>      POKE @target$,strLen
>
>
>      LONG IF UCASE$(test$)>UCASE$(target$)
>        temp&=PEEK LONG([indexHndl&]+((testElem&)*4))
>        POKE LONG [indexHndl&]+((testElem&)*4),PEEK
>LONG([indexHndl&]+((otherElem&)*4))
>        POKE LONG [indexHndl&]+((otherElem&)*4),temp&
>
>
>        testElem& = testElem& - split&
>      XELSE
>        testElem& = 0
>      END IF
>    UNTIL testElem& <= 0
>      NEXT thisElem&
>      split& = split& / 2
       DEC(count)
       FN showProgress(count)
>
>    WEND
>
>  END IF
>
>  CURSOR _arrowCursor
>END FN=indexHndl&
>
>
>Mark Arnold

Jay's version using XREF@'s
===========================
LOCAL FN QuickSort(dataHndl&,numRecs&,recSize,beginChar,strLen)
  DIM i&,split&,testElem&,thisElem&,elemNum&,otherElem&,whichPos&,temp&
  DIM recSize,strLen
  DIM test$,target$

  DIM   indexHndl&
  XREF@ indexHndl&(9999)
  DIM   dataH&
  XREF@ dataH$(9999)
  
  CURSOR _watchCursor
  indexHndl&=FN NEWHANDLE((numRecs&)*4)
  
  DEC(numRecs&)                                   'shift to zero based 
array
  
  LONG IF indexHndl&
    
    FOR i&=0 TO numRecs&                          'create index
      indexHndl&(i&) = i&
    NEXT
    split& = numRecs& / 2
    
    WHILE split& <> 0
      elemNum& = numRecs& - split&
      
      FOR thisElem& = 0 TO elemNum&
        testElem& = thisElem&
        
        DO
          otherElem& = testElem& + split&
          test$   = MID$(dataH$(indexHndl&(testElem&), beginChar,strLen)
          target$ = MID$(dataH$(indexHndl&(otherElem&),beginChar,strLen)
          
          LONG IF UCASE$(test$)>UCASE$(target$)
            SWAP indexHndl&(testElem&), indexHndl&(otherElem&)
            testElem& = testElem& - split&
          XELSE
            testElem& = 0
          END IF
          
        UNTIL testElem& <= 0
        
      NEXT thisElem&
      split& = split& >> 1
      
    WEND
    
  END IF
  
  CURSOR _arrowCursor
END FN = indexHndl&