Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

[Java] Quicksort code help.

  1. Oct 28, 2012 #1

    perplexabot

    User Avatar
    Gold Member

    Hi all. I am currently working on quicksort and have written the following code and gives "almost" good results. I am not too fond of the data structure I have chosen but it is too late for me to change. Lesson learned. Can anyone help me debug this thing. I have been at it for a while. Anyway here is the code:

    Code (Text):

            public static DLinkedList quickSort(DLinkedList unsortedList, int start, int finish){
    122                 int randpiv;
    123                 int offset = 0;
    124        
    125                 if(finish - start <= 0){
    126                         return unsortedList;
    127                 }
    128                 if(finish == -1){
    129                         randpiv = 0;
    130                 }else{
    131                         //fix here
    132                         if(finish - start == 0){
    133                                 randpiv = start;
    134                         }else{  
    135                                 randpiv =  start + myGen.nextInt(finish-start + 1);
    136                         }      
    137                 }      
    138                
    139                
    140                 for(int i = start; i < randpiv; i++){
    141                         if((long)unsortedList.distofElem(i) >= (long)unsortedList.distofElem(randpiv)){
    142                                 System.out.println("want to insert: " + unsortedList.distofElem(i) + " AFTER " + u    nsortedList.distofElem(randpiv));
    143                                 offset++;
    144                                 System.out.println("distofElem(randpiv) = " + unsortedList.distofElem(randpiv));
    145                                 DLNode moveMe = unsortedList.removeDist(unsortedList.distofElem(i));
    146                                 System.out.println("distofElem(randpiv) = " + unsortedList.distofElem(randpiv-1));
    147                                 unsortedList.insertAfter(moveMe, unsortedList.distofElem(randpiv-1));
    148                         }      
    149                 }      
    150                 for(int i = randpiv + offset + 1; i <= finish; i++){
    151                         if((long)unsortedList.distofElem(i) < (long)unsortedList.distofElem(randpiv)){
    152                                 System.out.println("want to insert: " + unsortedList.distofElem(i) + " BEFORE " + unsortedList.distofElem(randpiv));
    153                                 System.out.println("distofElem(randpiv) = " + unsortedList.distofElem(randpiv));
    154                                 DLNode moveMe = unsortedList.removeDist(unsortedList.distofElem(i));
    155                                 unsortedList.insertBefore(moveMe, unsortedList.distofElem(randpiv));
    156                         }      
    157                         randpiv++;
    158                 }
    159                 quickSort(unsortedList, start, randpiv - 1);
    160                 quickSort(unsortedList, randpiv + 1, finish);
    161                 return unsortedList;
    162         }
    (************************************************************************)
    35         //insert before an index//
     36         public void insertBefore(DLNode putMe, long distance){
     37                 for(temp = myRoot; temp.getDistance() != distance; temp = temp.next){
     38                         System.out.println("[in list for] tempdist = " + temp.getDistance());
     39                 }
     40                 System.out.println("Inserting: " + putMe.getDistance() + " BEFORE: " + temp.getDistance());
     41                 if(temp == myRoot){
     42                         myRoot.prev = putMe;
     43                         putMe.next = myRoot;
     44                         putMe.prev = null;
     45                         myRoot = myRoot.prev;
     46                 }else{
     47                         temp.prev.next = putMe;
     48                         putMe.prev = temp.prev;
     49                         temp.prev = putMe;
     50                         putMe.next = temp;
     51                 }
     52                 listLength++;
     53         }
     54
     55         //insert after an index//
     56         public void insertAfter(DLNode putMe, long distance){
     57                 for(temp = myRoot; temp.getDistance() != distance; temp = temp.next){
     58                         System.out.println(distance + " != " + temp.getDistance());
     59                         System.out.println("[in list for] tempdist = " + temp.getDistance());
     60                 }
     61                 if(temp == null){
     62                         System.out.println("NULLY!");
     63                 }
     64                 System.out.print("Inserting: " + putMe.getDistance() + " AFTER: ");
     65                 System.out.println(temp.getDistance());
     66                 if(temp == myTail){
     67                         myTail.next = putMe;
     68                         putMe.prev = myTail;
     69                         putMe.next = null;
     70                         myTail = myTail.next;
     71                 }else{
     72                         temp.next.prev = putMe;
     73                         putMe.next = temp.next;
     74                         temp.next = putMe;
     75                         putMe.prev = temp;
     76                 }
     77                 listLength++;
     78         }

     
    here is the input i feed it:
    29403 97291 7211 487075 10000000 9902 89600 1620 22500 180000 152 10 14700 1026046 6646 19769 17708 10201 16250 533026 1424561 880025 12930 91210 25004 580800 926718

    Here is the output i get:
    10
    152
    1620
    6646
    7211
    9902
    10201
    12930
    14700
    16250
    17708
    19769
    22500
    25004
    29403
    89600
    97291
    180000
    487075
    880025
    533026
    1424561
    91210
    10000000
    1026046
    580800
    926718

    which is close, but not quite.

    Thanks for reading.
     
    Last edited: Oct 28, 2012
  2. jcsd
  3. Oct 28, 2012 #2

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    Re: Quicksort code help.

    Shouldn't randpiv be a random number between start and finish, not 0 and finish?

    There may be more errors - I didn't look beyond that one.
     
  4. Oct 28, 2012 #3

    rcgldr

    User Avatar
    Homework Helper

    Re: Quicksort code help.

    You might want to add some if statements to compare for the problem values like

    Code (Text):

        if ( ... == 91210)
            print(" ");  // or any statement you can set a breakpoint on
     
    Then use a source level debugger to see what's going on.
     
  5. Oct 28, 2012 #4

    perplexabot

    User Avatar
    Gold Member

    Re: Quicksort code help.

    YES! thank you so much. You found an error! I will change my OP code accordingly with some other adjustments.

    I have already done if's and print pairs. I need to learn how to use valgrind with java. I used to know how to use it with C++ and C

    Thank you guys.
     
  6. Oct 28, 2012 #5

    perplexabot

    User Avatar
    Gold Member

    Hi I have updated my code but still not working properly. If anyone can help that would be great.
     
  7. Oct 28, 2012 #6

    gabbagabbahey

    User Avatar
    Homework Helper
    Gold Member

    Do you realize that the only time this last statement will execute is if finish==-1 and start<-2?

    Do you realize that this last statement will never get executed? You have already returned from the method when finish - start==0 thanks to your first if statement.

    what does myGen.nextInt(finish-start + 1) do?

    It woud be helpful if you posted your complete code (for all the custom classes you are using) since it is not at all obvious what some of these method calls do or what a DLNode is.

    Why are you incrementing your pivot (randpiv) inside this for loop?

    Are you planning and doing something with the result of these recursive calls to quicksort, or are you just doing extra processing for kicks? You haven't assigned the return parameter to anyting for these calls.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: [Java] Quicksort code help.
  1. Java help (Replies: 6)

Loading...