What is the number of comparisons using selection sort?
I have quick question about my program dealing with the number of
comparisons using selection sort. My program sorts an array of ints using
my selection sort class/method, display the sorted array, and it will
display the number of comparisons using my selection sort 2 class/method.
In my main/demo I have an array of 5 ints. It sorts them out fine but the
problem I am having is the number of comparisons. After I run it is says
it did 4 comparisons but shouldn't it be 10 instead? Due to the comparison
formula for selection being 1/2*n(n-1) or n(n-1)/2.
My selectionSort2 class/method is where my problem is. If you guys can
check out my selectionSort2 class/method that deals with the comparisons
and see what I am doing wrong I'll appreciate the help. It's the same as
my selectionSort class/method (which is right) but instead of sorting the
array, it just returns the amount of comparisons.
My demo:
ArrayInts[] myInts = new ArrayInts[5];
myInts[0] = new ArrayInts(3);
myInts[1] = new ArrayInts(9);
myInts[2] = new ArrayInts(6);
myInts[3] = new ArrayInts(1);
myInts[4] = new ArrayInts(2);
System.out.println("Unsorted array without using Selection Sort: ");
for(ArrayInts myInt:myInts){
System.out.println(myInt);
}
SelectionSort.selectionSort(myInts);
System.out.println(" ");
System.out.println("Sorted array using Selection Sort: ");
for(ArrayInts myInt:myInts){
System.out.println(myInt);
}
System.out.println(" ");
System.out.println("Number of comparisons using Selection Sort: " +
SelectionSort2.selectionSort2(myInts));
My selectionSort class/method that is used to only sort the array:
public class SelectionSort {
public static <T extends Comparable<? super T>> void selectionSort (T[]
data){
int min;
T temp;
for(int index=0; index < data.length-1; index++){
min = index;
for(int scan = index+1; scan < data.length; scan++)
if(data[scan].compareTo(data[min])<0)
min=scan;
temp = data[min];
data[min]=data[index];
data[index]=temp;
}
}
}
My ArrayInts class that is used to make the array:
public class ArrayInts implements Comparable<ArrayInts> {
public int num;
public ArrayInts(int initialNum) {
num = initialNum;
}
public String toString() {
return String.valueOf(num);
}
public int compareTo(ArrayInts other) {
int result;
if (num == other.num) {
result = 0;
} else if (num < other.num) {
result = -1;
} else {
result = 1;
}
return result;
}
}
My selectionSort2 class/method that is used to return the number of
comparisons:
public class SelectionSort2 {
public static <T extends Comparable<? super T>> int selectionSort2 (T[]
data){
int min;
T temp;
int comparisons=0;
for(int index=0; index < data.length-1; index++){
min = index;
for(int scan = index+1; scan < data.length; scan++)
if(data[scan].compareTo(data[min])<0)
min=scan;
temp = data[min];
data[min]=data[index];
data[index]=temp;
comparisons++;
}
return comparisons;
}
}
No comments:
Post a Comment