Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Bizzar Java sorting problem
New Posts  All Forums:Forum Nav:

Bizzar Java sorting problem

post #1 of 3
Thread Starter 
I'm writing a quick sort method. I know the code is messy, but we have to implement the quick sort using just one method. I'm running into a problem in my else clause of the actual quick sort method. I keep getting an Index Out of Bounds Exception when I try to assign smaller. However, this should NOT happen because I specify i to go up 1 less than the array size. I'm really puzzled by this. Any help would be appreciated.

Code:
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.List;
import java.util.Random;


public class Quicksort {
static public <E> List<E> sort(List<E> a, Comparator<E>c){
//ArrayList is used because it allows access to all members instantaneously.  
List<E> biggerthan = new ArrayList<E>();
if (a.size() >= 10){
Random rgen = new Random();
int pivot_index = rgen.nextInt(a.size());
E pivot = a.remove(pivot_index);
//System.out.printf("pivot is: %d%n", pivot);
Iterator<E> it = a.iterator();
while (it.hasNext()){
E temp = it.next();
//if the next item in the list is greater than or equal to the pivot
if (c.compare(temp, pivot)>=1){
biggerthan.add(temp);
it.remove();
}
}
sort(a, c);
sort(biggerthan, c);
}
else{
for (int i=0; i<a.size(); i++){
for (int b=i+1; b<a.size(); i++){
E bigger = a.get(b);
E smaller = a.get(i);
if (c.compare(smaller, bigger)>0){
a.set(i, bigger);
a.set(b, smaller);
}
System.out.println(a.toString());
}
}
for (int i=0; i<biggerthan.size(); i++){
for (int b=i; b<biggerthan.size(); i++){
E smaller = biggerthan.get(b);
E bigger = biggerthan.get(i);
if (c.compare(smaller, bigger)<0){
biggerthan.set(b, bigger);
biggerthan.set(i, smaller);
}
}
}
}
return null;

}

public static void main (String[] args){
List<Integer> b = new ArrayList<Integer>();
Random rgen = new Random();
for (int i=0; i<40; i++)
b.add(rgen.nextInt(20));
Collections.shuffle(b);
List<Integer> big =sort(b, new Comparator<Integer>(){
public int compare(Integer a, Integer b){return a-b;};
});
for (int d=0; d<big.size(); d++){
System.out.println(big.get(d));
}
}
}
post #2 of 3
Code:
...
for (int i=0; i<a.size(); i++){
for (int b=i+1; b<a.size(); i++){
E bigger = a.get(b);
E smaller = a.get(i);
if (c.compare(smaller, bigger)>0){
a.set(i, bigger);
a.set(b, smaller);
}
System.out.println(a.toString());
}
}

The second for loop is adding 1 so the first loop can't loop to the last item, it has to stop one earlier so the first loop should be:

for (int i=0; i<a.size()-1; i++){
i7
(13 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 920 D0 w/ HT On [4.01ghz @ 1.208v] Asus P6X58D Premium Asus HD5870 G.SKILL 6GB (3X2GB) DDR3 @ 1528MHz 
Hard DriveOptical DriveOSMonitor
OCZ Vertex Turbo 60GB FW1.5 2xSamsung Spinpoint F3 LG 8x Blu-ray Combo Drive Windows 7 64-bit Dell U2410 Rev. A04 
PowerCase
OCZ ModXStream Pro 700W V2.2 HAF 922 
  hide details  
Reply
i7
(13 items)
 
  
CPUMotherboardGraphicsRAM
Intel Core i7 920 D0 w/ HT On [4.01ghz @ 1.208v] Asus P6X58D Premium Asus HD5870 G.SKILL 6GB (3X2GB) DDR3 @ 1528MHz 
Hard DriveOptical DriveOSMonitor
OCZ Vertex Turbo 60GB FW1.5 2xSamsung Spinpoint F3 LG 8x Blu-ray Combo Drive Windows 7 64-bit Dell U2410 Rev. A04 
PowerCase
OCZ ModXStream Pro 700W V2.2 HAF 922 
  hide details  
Reply
post #3 of 3
Thread Starter 
Quote:
Originally Posted by sidcitris View Post
Code:
...
for (int i=0; i<a.size(); i++){
for (int b=i+1; b<a.size(); i++){
E bigger = a.get(b);
E smaller = a.get(i);
if (c.compare(smaller, bigger)>0){
a.set(i, bigger);
a.set(b, smaller);
}
System.out.println(a.toString());
}
}

The second for loop is adding 1 so the first loop can't loop to the last item, it has to stop one earlier so the first loop should be:

for (int i=0; i<a.size()-1; i++){
Of course. It's always something stupid. ALWAYS!!!. GAWD I suck at programming. Thanks for the help.
New Posts  All Forums:Forum Nav:
  Return Home
  Back to Forum: Coding and Programming
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Bizzar Java sorting problem