Announcement

Collapse
No announcement yet.

convert a little java to PB

Collapse
X
 
  • Filter
  • Time
  • Show
Clear All
new posts

  • Michael Mattias
    replied
    :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?

    Leave a comment:


  • Michael Mattias
    replied
    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)

    Leave a comment:


  • John Gleason
    replied
    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.

    Code:
    #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

    Leave a comment:


  • Chris Holbrook
    replied
    Originally posted by Paul Franks View Post
    ... 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....

    Code:
    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
    Last edited by Chris Holbrook; 9 Jun 2008, 02:19 AM. Reason: confused John & Paul

    Leave a comment:


  • Paul Franks
    replied
    Originally posted by Chris Holbrook View Post
    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.

    Leave a comment:


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

    Leave a comment:


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

    Leave a comment:


  • John Gleason
    replied
    Fwiw, here's the whole function.

    Code:
    '   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.

    Code:
    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

    Leave a comment:


  • John Gleason
    replied
    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.

    Leave a comment:


  • Chris Holbrook
    replied
    or was it
    Code:
             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
    ???

    Leave a comment:


  • Chris Holbrook
    replied
    guesswork!

    Code:
    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

    Leave a comment:


  • Donald Darden
    replied
    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:
    Code:
    '                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:

    Code:
      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.
    Last edited by Donald Darden; 8 Jun 2008, 03:02 PM.

    Leave a comment:


  • Mr. Kevin Diggins
    replied
    Removed by poster
    Last edited by Mr. Kevin Diggins; 8 Jun 2008, 01:47 PM.

    Leave a comment:


  • John Gleason
    started a topic convert a little java to PB

    convert a little java to PB

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

    Code:
    '                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
Working...
X