Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Median of 3 quicksort
New Posts  All Forums:Forum Nav:

Median of 3 quicksort

post #1 of 9
Thread Starter 
Hey guys im learning quick sorts in class but on linked lists not on arrays and our prof tells us about median of 3 which sounds like an easy enough thing to recreate but of course its harder than i thought it would have been so i need some help. I have all the quick sort as the prof has given and im working in the chooseAndRemovePivot method. I find the initial middle and compare but i cant keep it going and i dont see why.
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
post #2 of 9
Define "Can't Keep it going".

Is it unstable?
post #3 of 9
Compiling and running his code, it appears he is having some null pointer exceptions. I'll see if I can pin point any issues.
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
post #4 of 9
Here is a problem I see in your chooseAndRemovePivot() method (I changed the size of the list to something more manageable. I also suggest that you use fixed elements in the list until you know the sorting works. That way you don't get new numbers in the list every time you run the program, creating a different sorting situation to debug).
Code:
if(first.getData() > mid.getData()){
pivot = mid;
mid = pivot.getNext();
size--;
}

if(first.getData() > last.getData()){
pivot = last;
last = pivot.getNext();
size--;
}
if(mid.getData() > last.getData()){
pivot = last;
        last = pivot.getNext();
size--;
}


Lets assume we have this list: [645, 765, 194, 440, 477, 853, 486]

The middle index of the list is 3. The element at index 3 is 440 (assuming the first starts at index 0). Therefore, the first (645) is greater the mid (440). So you say pivot = mid, or in other words, pivot = 440. Then you say that the mid = pivot.getNext(), so mid = 440.getNext() = 477.

After that you look at the next if-statement and it is true (first > last). So the pivot becomes last, pivot = 486. Then you say last = 486.getNext() = NULL because the pivot is the end of the list and the next element after the end is NULL.

Now is the problem. You evaluate the next if statement and say (... > last.getData()). You just requested data from a NULL element, because last was set to NULL in your previous if-statement block. That will generate a null pointer exception.

I have never really used the LinkedList class in Java, so I dunno the specifics, but as far as I know, trying to access the data of a NULL node won't work.

Adding in some print statements illustrates what I mean (I added in the last print statement when typing this post, to illustrate it; I didn't actually have that in the code or else I would have generated the exception when trying to print last.getData(), before actually calling it in the third if-statement).
Code:
$ javac Quicksort.java 
$ java Quicksort
Before sorting:
[ 645, 765, 194, 440, 477, 853, 486 ] size= 7

middle index = 3
mid data = 440

(first > mid) == TRUE
pivot = mid ==>645 = 440
mid = pivot.getNext() ==> 440 = 447

(first > last) == TRUE
pivot = last ==>440 = 486
last = pivot.getNext() ==> 486 = NULL

Exception in thread "main" java.lang.NullPointerException
at LinkedList.chooseAndRemovePivot(Quicksort.java:108)
at LinkedList.quicksort(Quicksort.java:63)
at Quicksort.main(Quicksort.java:20)
$

Edited by Tomiger - 6/12/11 at 12:17am
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
post #5 of 9
+1 Tom nailed it, I didn't have time to look over the code much until now.
post #6 of 9
Thread Starter 
So its in my if statements not in my way of finding what mid is. Thank you i'll look more at the psuedo code and at the code used for arrays and try to figure it out. Also sorry for th elate reply i was out of town with no wifi.
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
post #7 of 9
To be honest, I didn't look very much at how the algorithm was working; I just went where the errors lead me. Let us know how it comes along or if you get stuck somewhere with the algorithm.
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
 
Mineral Oil PC
(7 items)
 
 
CPUMotherboardGraphicsRAM
Intel Core i7 4790K Devil's Canyon 4.0GHz ASUS Sabertooth Z97 Mark S (White) Zotac GTX 760 Avexir Raiden 16GB DDR3 
Hard DriveCoolingCoolingCooling
OCZ Trion 240GB XSPC Raystorm Pro (white) XSPC EX 240 (white) XSPC EX 360 (white) 
CoolingCoolingCoolingCooling
Swiftech MCP655 Monsoon Dual Bay Reservoir Monsoon Modular Tube Reservoir Monsoon Stand Alone Pump Top/Cover 
CoolingPower
EK GTX 970 Water Block Corsair AX760i 
CPUMotherboardGraphicsGraphics
Intel Core i7 2600K Sandy Bridge 3.4 GHz Gigabyte GA-P67A-UD4-B3 GTX 285 GTX 285 
RAMHard DriveHard DriveCooling
Corsair Vengeance 16GB Western Digital 1TB Western Digital 250GB EK-Supremacy Clean CSQ - Nickel 
CoolingCoolingCoolingCooling
XSPC RX 360 XSPC EX 360 (cross flow) FrozenQ T-virus Reservoir EK Waterblock GTX 285 
Cooling
Swiftech MCP655 
  hide details  
Reply
post #8 of 9
Thread Starter 
So far ive made 6 if statements one to cover every possibility of which value is the median of the 3, so now im actually reaching the next method but my pivot is returning as null. Im trying to figure out where the pivot is coming from in the if statements.

edit: using random numbers it appears as though i am reaching the appropriate statement block but pivot is not being returned properly as of yet i am not sure why but i will let you know if i find out. If i give up i will let you know also... lol
Edited by Sin Cities Sin - 6/13/11 at 9:59am
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
post #9 of 9
Thread Starter 
Ok im pretty sure i have found the error and it is in the way that the middle is found i always start from the beginning but i dont think that is always right when testing my code the items before the pivot are proper but after they are not. Printing out the first mid and last nodes when i get to the after part of the pivot i get weird things in which the mid and last are the same. Im sure it will make more sense if someone runs this and see's what im trying to say. I also re did the way that a node is removed by using a previous pointer which should remove a node without updating the current pivot (the logic works in my head). Please let me know if im on the right track and maybe an idea of how to find the middle properly
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
My Rig
(13 items)
 
  
CPUMotherboardGraphicsRAM
i7 860 Asus P7P55D PRO GTX 480 sli wc Corsair Vengeance  
Hard DriveOSPowerCase
WD 1TB BLACK x2 Windows 7 64 bit Silverstone Strider 1000+ CM 690 2 Advanced 
  hide details  
Reply
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Median of 3 quicksort