Java Debugging Java Quicksort Code: Tips and Tricks for Optimal Results

  • Thread starter Thread starter perplexabot
  • Start date Start date
  • Tags Tags
    Code Java
AI Thread Summary
The discussion revolves around debugging a quicksort implementation using a doubly linked list. The original poster expresses dissatisfaction with their data structure choice and seeks help in resolving issues with their code. Key points include confusion over the pivot selection, where it is suggested that `randpiv` should be a random number between `start` and `finish`, not between `0` and `finish`. The poster acknowledges an error related to the `finish` condition and considers using debugging techniques, such as adding conditional statements for specific values and utilizing a source-level debugger.Further feedback highlights logical flaws in the code, such as unreachable code due to prior return statements and the improper handling of the pivot increment within loops. Additionally, there is a call for more context about custom classes used in the implementation, particularly the `DLNode` class, to better understand method functionalities. The discussion emphasizes the need for clarity in recursive calls and the importance of correctly managing the pivot during the sorting process.
perplexabot
Gold Member
Messages
328
Reaction score
5
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: 
        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:
Technology news on Phys.org


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.
 


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

Code: 
    if ( ... == 91210)
        print(" ");  // or any statement you can set a breakpoint on

Then use a source level debugger to see what's going on.
 


AlephZero said:
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.
YES! thank you so much. You found an error! I will change my OP code accordingly with some other adjustments.

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

Code: 
    if ( ... == 91210)
        print(" ");  // or any statement you can set a breakpoint on

Then use a source level debugger to see what's going on.
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.
 
Hi I have updated my code but still not working properly. If anyone can help that would be great.
 
perplexabot said:
Code: 
125                 if(finish - start <= 0){
126                         return unsortedList;
127                 }
128                 if(finish == -1){
129                         randpiv = 0;

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

Code: 
130                 }else{
131                         //fix here
132                         if(finish - start == 0){
133                                 randpiv = start;

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.

Code: 
134                         }else{  
135                                 randpiv =  start + myGen.nextInt(finish-start + 1);

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

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

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.

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

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

Code: 
159                 quickSort(unsortedList, start, randpiv - 1);
160                 quickSort(unsortedList, randpiv + 1, finish);

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.
 

Thread 'Learning Assembly and computer architecture for x86'

Dear Peeps I have posted a few questions about programing on this sectio of the PF forum. I want to ask you veterans how you folks learn program in assembly and about computer architecture for the x86 family. In addition to finish learning C, I am also reading the book From bits to Gates to C and Beyond. In the book, it uses the mini LC3 assembly language. I also have books on assembly programming and computer architecture. The few famous ones i have are Computer Organization and...
View full post »

Thread 'Touch-typing for programmers'

What percentage of programmers have learned to touch type? Have you? Do you think it's important, not just for programming, but for more-than-casual computer users generally? ChatGPT didn't have much on it ("Research indicates that less than 20% of people can touch type fluently, with many relying on the hunt-and-peck method for typing ."). 'Hunt-and-peck method' made me smile. It added, "For programmers, touch typing is a valuable skill that can enhance speed, accuracy, and focus. While...
View full post »

Thread 'Microsoft Technical Interview question'

I had a Microsoft Technical interview this past Friday, the question I was asked was this : How do you find the middle value for a dataset that is too big to fit in RAM? I was not able to figure this out during the interview, but I have been look in this all weekend and I read something online that said it can be done at O(N) using something called the counting sort histogram algorithm ( I did not learn that in my advanced data structures and algorithms class). I have watched some youtube...
View full post »

Hot Threads

Recent Insights

Back
Top