I was recently assigned to do a lab assignment in which i needed to find the amount of steps each type of sorting algorithm takes to sort a list of 100, 200, 400, and 800 integers... (Bubble Sort, Selection Sort, Insertion Sort) So far this is what I've done.
public void Bubble(int rolls){
ArrayList <Integer> list = new ArrayList <Integer> ();
int counter = 0;
int rollcount = 0;
int rollcount2 = rolls;
while(rollcount != rolls){
//for (int outer = 0; outer < list.size() - 1; outer++){
counter = counter + 1;
//for (int inner = 0; inner < list.size()-outer-1; inner++){
counter = counter + 1;
//if (list.get(inner) > list.get(inner + 1)){
// int temp = list.get(inner);
// list.set(inner, list.get(inner + 1));
// list.set(inner + 1, temp);
counter = counter + 4;
rollcount2 = rollcount2 - 1;
counter = counter + rollcount2;
rollcount = rollcount + 1;
}
//}
//}
//}
System.out.println("BubbleSort went through "+counter+" steps.");
}
void Select(int rolls){
int counter = 0, rollcount = 0, rollcount2 = rolls;
while(rollcount!=rolls){
//for (int outer = 0; outer < list.size() - 1; outer++){
//min = outer;
counter = counter + 2;
//for (int inner = outer + 1; inner < list.size(); inner++){
counter = counter + 1;
//if (list.get(inner) < list.get(min)) {
counter = counter + 1;
//min = inner; // a new smallest item is found
//}
//}
//temp = list.get(outer);
//list.set(outer, list.get(min);
//list.set(min, temp);
counter = counter + 6;
rollcount = rollcount + 1;
}
//}
System.out.println("SelectionSort went through "+counter+" steps.");
}
void Insert(int rolls){
int rollcount = 0, counter = 0;
while(rollcount != rolls){
//for (int outer = 1; outer < list.size(); outer++){
//int position = outer;
//int key = list.get(position);
counter = counter + 3;
//while (position > 0 && list.get(position ? 1) > key){
//list.set(position, list.get(position ? 1));
//position--;
//}
//list.set(position, key);
counter = counter + 5;
rollcount = rollcount + 1;
//}
}
System.out.println("InsertionSort went through "+counter+" steps.");
}
AND the output with 100 integers
BubbleSort went through 5550 steps.
SelectionSort went through 1000 steps.
InsertionSort went through 800 steps.
I just wanted to get someone elses opinion because these numbers dont seem right to me... I thought that the insertion would have a lot less steps then the selection and so on. All i do is everytime I find a step the computer takes to move the number i add 1 to the counter, and everytime 1 number is swapped i add 1 to the counter... Just looking for some further feed back to get another helpful view on what im trying to do. Thanks!