- #1
perplexabot
Gold Member
- 329
- 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:
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.
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: