convert a little java to PB

[John Gleason]

I am trying to translate a little java code, but have been unsuccessful with the snippet below. Any help would be appreciated.

'                for(;;)
'                {
'                        while(a[++i]<v);
'                        while(a[--j]>v);
'                        if (j<i) break;
'                        swap (a,i,j);
'                }

'here's the swap function, but I'm almost sure that's not the problem because
'my translation works fine in another program.

'    private void swap(int a[], int i, int j)
'    {
'            int T;
'            T = a[i];
'            a[i] = a[j];
'            a[j] = T;
'    }

'below is what I imagined it might be, but it is not working.
      INCR i
      DECR j
      WHILE a(i) < v
         WHILE a(j) > v
            IF j < i THEN EXIT FUNCTION
            SWAP a(j), a(i)
            DECR j
         WEND
         INCR i
      WEND

[Mr. Kevin Diggins]

Removed by poster

[Donald Darden]

IF you see a statement like a(++J), it means that J is incremented before it
is used. If you see a(j++), the increment takes place after it is used.

PowerBasic does not give you the ability to perform increments and decrements
implicitly at time of use. You have to determine which is to be done, before or after, and perform that step separately with an INCR or DECR statement.

Your problem here is trying to retain the same WHILE statement structure, but
it involves the use of implicit increment and decrement, So obviously you have to consider what the statement does and duplicate that, even though it will require more steps.

Now let;s look at your statement again:

'                for(;;)
'                {
'                        while(a[++i]<v);
'                        while(a[--j]>v);
'                        if (j<i) break;
'                        swap (a,i,j);
'

}
The "for(;" means an infinite loop. We can do the same with DO...LOOP
The "while(a(++i)<v)" would have to be broken down into several steps. I will attempt a complete translation here:

  DO
      DO
         INCR i
         IF a(i)<v THEN 
           DO
              DECR J
              IF a(j)>v THEN
                IF j<i THEN GOTO break
                SWAP a(i),a(j)
              END IF
           LOOP
         END IF
      LOOP
  LOOP
break:

However, the code example does not look complete to me. Normally, you have to have some way of establishing what "v" is, which is often the midpoint of the array initially, and you do not establish the initial values of i and j. Further, this approach to sorting an array usually leads to a recursive process

But the code looks flawed logically as well. If i<v and j>v, then when would j be less than i? To resolve this, you would have to check for j<i before you check for j>v.

There are any number of sort methods implemented in PowerBasic. You don't need to try and transcribe one from another language. In fact. since PowerBasic supports a very fast ARRAY SORT capability, you can just learn to rely on that rather than write your own.

[Chris Holbrook]

guesswork!

do  
    do until a(i) < v : incr i : loop
    '
    do until a(j) > v : decr j : loop
   '
    if j < i then exit loop

    swap (a, i j) ' dunno what swap does! 
loop

[Chris Holbrook]

or was it

         DO
            DO : INCR i : LOOP UNTIL a(i) < v
            '
            DO  : DECR j : LOOP UNTIL a(j) > v
            '
                       IF j < i THEN EXIT LOOP

            'swap (a, i j) ' dunno what swap does!
        LOOP

???

[John Gleason]

Donald, you are correct sir, the code is from a little java sorting algorithm. You must have a high ESP (extra super PowerBasic-er) quotient to have figured that out from so little code. Yes, I too use the array sort of PB just about exclusively, but saw this little demo and wondered how it worked more just out of curiosity.

[John Gleason]

Fwiw, here's the whole function.

'   private void QuickSort(int a[], int l, int r) throws Exception
'   {
'        int M = 4;
'        int i;
'        int j;
'        int v;
'
'        if ((r-l)>M)
'        {
'                i = (r+l)/2;
'                if (a[l]>a[i]) swap(a,l,i);     // Tri-Median Methode!
'                if (a[l]>a[r]) swap(a,l,r);
'                if (a[i]>a[r]) swap(a,i,r);
'
'                j = r-1;
'                swap(a,i,j);
'                i = l;
'                v = a[j];
'                for(;;)
'                {
'                        while(a[++i]<v);
'                        while(a[--j]>v);
'                        if (j<i) break;
'                        swap (a,i,j);
                }
'                swap(a,i,r-1);
'                QuickSort(a,l,j);
'                QuickSort(a,i+1,r);
'        }
'    }

And here's what I have for it, which seems to do one sort pass, but then stops.

FUNCTION QuickSort(BYVAL lf AS LONG, BYVAL r AS LONG) AS LONG
   LOCAL m,i,j,v AS LONG
   m = 4
   IF r-1 > m THEN
      i = r+1 / 2
      IF a(lf) > a(i) THEN SWAP a(lf), a(i)
      IF a(lf) > a(r) THEN SWAP a(lf), a(r)
      IF a(i ) > a(r) THEN SWAP a(r ), a(i)

      j = r-1
      SWAP a(j ), a(i)
      i = lf
      v = a(j)

      DO
         INCR i
         IF a(i)<v THEN
           DO
              DECR J
              IF a(j)>v THEN
                IF j<i THEN
                   EXIT FUNCTION 
                END IF
                SWAP a(i),a(j)
              END IF
           LOOP
         END IF
      LOOP

      SWAP a(r-1), a(i)
      quickSort(lf, j)
      quickSort(i+1, r)
   END IF
END FUNCTION

[John Gleason]

And btw Chris, the swap just swaps a(i) and a(j) in your code example.

[Chris Holbrook]

I don't know Java but I do suspect that the whiles are not nested.

[Paul Franks]

I don't know Java but I do suspect that the whiles are not nested.

You're right about that, the semicolons terminate the while loops, just like C.

while(a[++i]<v);

This increments i until a[i] <v, then goes to the next statement.

while(a[--j]>v);

This decrements j until a[j]>v, then goes to the next statement.

Chris has it right.

[Chris Holbrook]

... just like C.

Still, my heart!

There was also a bit if confusion with l, 1 and lf. I tried to make a PB translation but that GPFs too, probably because j goes hugely negative. I would like to have more confidence in the origin and its transcription before trying harder. Also, John, there are several quicksorts listed in these fora which probably work!

Now, if you'd asked for a java to PB translator....

SUB QuickSort(BYVAL b AS DWORD, lf AS LONG, r AS LONG)
    LOCAL m,i,j,v AS LONG
    LOCAL a() AS LONG

    REDIM a(0 TO 999) AT b
    m = 4
    IF (r - lf) > m THEN
        i = (r + lf) / 2
        IF a(lf) > a(i) THEN SWAP a(lf), a(i)
        IF a(lf) > a(r) THEN SWAP a(lf), a(r)
        IF a(i ) > a(r) THEN SWAP a(r ), a(i)

        j = r-1
        SWAP a(j ), a(i)
        i = lf
        v = a(j)

        DO
           DO
               INCR i
           LOOP UNTIL  a(i) = v
           DO
               DECR j
           LOOP UNTIL a(j) = v
           IF j < i THEN EXIT LOOP
           SWAP a(i),a(j)
        LOOP

        SWAP a(r-1), a(i)
        quickSort(BYVAL VARPTR(a()),lf, j)
        quickSort(BYVAL VARPTR(a()),i + 1, r)
    END IF
END SUB

[John Gleason]

Thanks Chris, I didn't have time to try your un-nested code yesterday, but with a couple mods, it does sort most of the way now. The remaining sorting in the demo that this code came from is done by an insertion sort.

I've got to believe it's close to a correct translation, but like you said, why not check for some quicksorts (or others) on the PB forums? dooohh.

#COMPILE EXE
#DIM ALL
GLOBAL a() AS LONG

FUNCTION QuickSort(BYVAL lf AS LONG, BYVAL r AS LONG) AS LONG
   LOCAL m,i,j,v AS LONG
   m = 4
   IF r-1 > m THEN
      i = r+1 / 2
      IF a(lf) > a(i) THEN SWAP a(lf), a(i)
      IF a(lf) > a(r) THEN SWAP a(lf), a(r)
      IF a(i ) > a(r) THEN SWAP a(r ), a(i)

      j = r-1
      SWAP a(j ), a(i)
      i = lf
      v = a(j)

      DO
          INCR i
      LOOP WHILE  a(i) < v
      DO
          DECR j
      LOOP WHILE a(j) > v
      IF j < i THEN EXIT FUNCTION
      SWAP a(i),a(j)

      SWAP a(r-1), a(i)
      quickSort(lf, j)
      quickSort(i+1, r)
   END IF
END FUNCTION

FUNCTION PBMAIN () AS LONG
  LOCAL barLen, x, length AS LONG
  LOCAL xstr AS STRING
  length = 1000
  barLen = 1
  
  DIM a(length) AS LONG
  DO
     x = RND(0, length - 1)
     IF a(x) = 0 THEN
        a(x) = barLen
        INCR barLen
        IF barLen = length THEN EXIT DO
     END IF
  LOOP
  FOR x = 0 TO length - 1
     xstr = xstr & STR$(a(x))
  NEXT
  ? xstr
  
  RESET xstr
  quickSort(0, length - 1)
  FOR x = 0 TO length - 1
     xstr = xstr & STR$(a(x))
  NEXT
  ? xstr
END FUNCTION

[Michael Mattias]

If you wanted to do a QuikSort, there simply must be an example in the source code forum. (I have not looked, since I have such code in my personal library, and so should every PB programmer have such a function in his/her personal library).

Why mess around with "convert from Java" if you could have just found some PB "QuikSort" code???

Verb-for-verb-translation = stone loser (again)

[Michael Mattias]

:doh:

For that matter, ARRAY SORT might have been even easier. Who cares what sorting algorithm is used, as long as the array (small 'a') ends up sorted?