Announcement

Collapse

Maintenance

The forum could be offline for 30-60 minutes in the very near future for maintenance (said 3pm Pacific). I was behind on getting this notice. I do apologize.
See more
See less

convert a little java to PB

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

  • 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

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

    Comment


    • #3
      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.

      Comment


      • #4
        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

        Comment


        • #5
          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
          ???

          Comment


          • #6
            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.

            Comment


            • #7
              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

              Comment


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

                Comment


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

                  Comment


                  • #10
                    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.
                    --pdf

                    Comment


                    • #11
                      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

                      Comment


                      • #12
                        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

                        Comment


                        • #13
                          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
                          Tal Systems Inc. (retired)
                          Racine WI USA
                          [email protected]
                          http://www.talsystems.com

                          Comment


                          • #14
                            :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?
                            Michael Mattias
                            Tal Systems Inc. (retired)
                            Racine WI USA
                            [email protected]
                            http://www.talsystems.com

                            Comment

                            Working...
                            X