I have a program that allows a user to input an integer value into an applet (the number entered determines the size of a list). From the value entered the program determines how many comparisons are required to sort the list using the size inputted. The applet is working but the program is just printing out a sorted list instead of the comparison required. I need help finishing up my code. Please and thank you.

import java.util.*;         //supplies random class
import java.awt.*;          //supplies user interface classes
import java.awt.event.*;    //supplies event cleasses
import java.applet.Applet;  //supplies applet class

public class TestingUse extends Applet implements ActionListener
{
public void actionPerformed(ActionEvent event)    //event handler method
{
size = Short.parseShort(inputField.getText());   //gets integer input from user
values = new int[size];                          //generate the size
initValues(size);                               //fill the array
selectionSort();                                //sort the array
inputField.setText("");                         //resets input field
printValues();

outLabel.setText("The comparison is: " + what????);

}
void initValues(int size)                     //gets number of values and randomly generates values
{
Random rand = new Random();
for (int index = 0; index < size; index++)
values[index] = Math.abs(rand.nextInt()) % size;
}

int minIndex(int startIndex, int endIndex)    //finds the smallest value in the array and swaps it with the first value
{                                             //in the array position
int indexOfMin = startIndex;
for (int index = startIndex + 1; index <=endIndex; index++)

if (values[index] < values[indexOfMin])
indexOfMin = index;

return indexOfMin;
}

public void swap(int index1, int index2)  //swaps the integers at location index1 and index2 of array values
{
int temp = values[index1];
values[index1] = values[index2];
values[index2] = temp;
}

void selectionSort()                    //the elements in the array values are sorted
{
int endIndex = size - 1;
for (int current = 0; current < endIndex; current++)
swap(current, minIndex(current, endIndex));
}

void printValues()
{
int value;
for (int index = 0; index < size; index++)
{
value = values[index];
if(((index -1)*index)/2 ==0)  //this formula is not doing what I want
System.out.println(value);
else
System.out.println(value + " ");
}
System.out.println();
}


//declare fields for applet viewer
private TextField inputField;
private int[] values;
private int size;
private Label outLabel;
private Button button;

//init method - to set up fields and buttons on applet

public void init()
{
Label label;
label = new Label("Enter # for comparison ");
button = new Button("enter");
button.addActionListener(this);
inputField = new TextField("Value");
outLabel = new Label("The number of comparisons is: ");
add(label);
add(inputField);
add(button);
add(outLabel);
setLayout(new GridLayout(5,0));
}
}

So my first question would be: what are you comparing? I only see that you've implemented the Selection Sort... are you wanting to compare different methods of carrying out the selection sort?

Next, your criteria for comparison isn't clear. Runtime seems like the best criteria and would require that you keep track of the time the event was started and when the event ended.

Finally, I don't see what that formula in your printValues() method is suppose to do? Since you're using a println() the output should be seemingly the same if the condition is true or false.

At this point I am just completely confused. It is not supposed to calculate the time it takes - although that would make more sense. I want it to calculate the number of comparisons it takes to sort a list - if the user enters a list value of 100 it should return a comparison value of 4950 (I'm assuming swaps to sort the list)

Oh!! My bad, I completely read the question incorrectly... actually I was so off I wonder how I managed to confuse myself that much lol

You aren't keep track of the number of comparisons you're doing. In your algo, each time the loop runs, there will be a swap. So for 100 numbers there will be 100 swaps. Is this the same algo your teacher/lecturer gave for this problem? There are other methods of doing the selection sort that would seem more applicable to counting the number of comparisons.

Regardless, it seems you want to count the number of comparisons in which case you'd keep a counter hehe just an int variable that increments each time you compare values (which in your case seems to be a set number of times that can be deduced by a mathematical formula as opposed to the need of counting).

Hope this makes sense.

Yeah that what I want to do, the tutor has given us the example that a list of 100 would require 4950 comparisons. Unfortunately I don't know how to do that in my code. I know the code is wrong but I really don't know how to change it.

I wouldn't say your code is wrong... like I said, the selection sort can be done in many ways. Here's the algo from Wikipedia:

for i ← 0 to n-2 do
    min ← i
    for j ← (i + 1) to n-1 do
        if A[j] < A[min] //this is the comparison
            min ← j
    swap A[i] and A[min]

Wikipedia goes on to explain "selecting the lowest element requires scanning all n elements (this takes n − 1 comparisons) and then swapping it into the first position."

What that means for you is that if you have 10 elements then you'll be doing 10 - 1 comparisons the first time the loops runs, then 9 - 1 comparisons the next time the loop runs and so on. In this way, you can actually use this loop to count the number of comparisons:

int comp = 0;
for (int k = 0; k <= n - 2; k++)
    comp += n - 1 - k;

Simply put, each time the loop runs, there will be one less comparison. Also, since you don't ever compare the first element with itself and you don't need to compare the last element with anything, the k loop runs to n - 2 where n is the number of elements.

And in retrospect, when I said: "There are other methods of doing the selection sort that would seem more applicable to counting the number of comparisons," I think I was mistaken.

I think I might just give up on this one. The assignment can't we worth that much.

thanks for trying to help.

It's just one single calc to determine the number of comparisons and you have the formula right there in your code - you just aren't using the correct value in it. I'll give you a hint: n is the number of elements in your values array.

uh hum I just gave you the answer! If you run the loop I gave you and set n to 100 you'll see that comp will have a final value of 4950.

But the idea is rather simple, you can count individual comparisons yourself. Declare a class attribute int count; (note that this class attribute will automatically be assigned the value 0) then instead of:

if (values[index] < values[indexOfMin])
indexOfMin = index;

You will have:

if (values[index] < values[indexOfMin])
{
    indexOfMin = index;
    count++;
}

Edited 3 Years Ago by Reverend Jim: Fixed formatting

He already has the calculation right there in his method. It was just not utilized correctly. The number of comparisons necessary for n elements is n(n − 1) / 2 .

I know I should be getting, I am as frustrated with myself as I'm sure you guys are with me, but I have tried different things in my calculations and I am still getting the same results. The numbers in the array printing out not the number of comparisons.

Well, that does seem to be the point of a "printValues()" method, yes? The calculation for the number of comparisons has nothing to do with that method and nothing to do with a loop. It is one calculation that only requires the number of elements being sorted.

I walked away from this and when I came back it all made sense. I had my calculation on the wrong line. I should have walked away earlier since I wasn't even making sense in my asking questions.

This question has already been answered. Start a new discussion instead.