dimanche 8 mars 2015

Infinite Loop when using vector.size() in for loop's condition statement



I was implementing Bucket Sort and using insertion sort for sorting each bucket. But when I ran the code it went into an infinite loop. After debugging, I found that the for loop was running infinitely.



// we have buckets for each intervals
// we add values into each bucket
// each bucket is then sorted at the end
// then all the buckets are merged together
public class BucketSort {


@SuppressWarnings("unchecked")
private Vector<Double>[] buckets = new Vector[10];


private int sizeOfInput;

//constructor

public BucketSort(int size){
sizeOfInput = size;
for(int i=0; i<10;i++){
buckets[i] = new Vector();

}

}


public static void main(String args[]){
Double[] arr = {0.11,0.12,0.21,0.61,0.7,0.5,0.14,0.2,0.61,0.65,0.72,0.80,0.98,0.82,0.96,0.35,0.47,0.53};

BucketSort s = new BucketSort(arr.length);

Vector result = s.bucketSort(arr);
System.out.println("The result is : ");

for(int i= 0;i< result.size();i++){
System.out.println(result.get(i));
}
//s.printBucket();
}

public void printBucket(){
// prints out the elements in each bucket
for(int i = 0; i<10;i++){
System.out.println("The bucket "+ i + " contains these elements");
for(int j=0; j<buckets[i].size();j++){

System.out.println(buckets[i].get(j));
}
}
}


public Vector bucketSort(Double[] arr){
// add the elements in appropriate buckets
for(int i = 0; i<arr.length;i++){
for(int j=0; j<10;j++){
if(arr[i] < (double)(j+1)/10){
buckets[j].add((double)arr[i]);
break;
}
}
}

// print out each bucket
printBucket();

// call the sort function on each of the buckets
for(int i= 0 ; i< 1; i++){

sort(1);
System.out.println("Sorted bucket" + i);
}


return merge();
}

public void sort(int number){

//binary sort each values of vector
System.out.println("bucket" + number + "size is " + buckets[number].size());
int k = buckets[number].size();

for(int i = 1; i < (buckets[number].size()); i++ ){
System.out.println("Bucket" + number + "element" + i);

double a = buckets[number].get(i);
int j= i;
while(j > 0 && buckets[number].get(j-1) > a){
//double b = buckets[no].get(j-1);
//buckets[no].add(j,b);
j--;
System.out.println("Sorting bucket" + number);
}

buckets[number].add(j,a);

}
}

public Vector merge(){
//merge all the bucket vectors into an array
Vector<Double> result = new Vector();

for(int j=0;j<10;j++){
//buckets[j].copyInto(result);
result.addAll(buckets[j]);
}

return result;
}


}


If I replace



for(int i = 1; i < (buckets[number].size()); i++ ){


with



for(int i = 1; i < k; i++ ){


where k = buckets[number].size()


This solved the problem but I didn't understand why did the error occur in the first place. Please explain the reason for such inappropriate behavior.




Aucun commentaire:

Enregistrer un commentaire