| | |
Selection Sort Method + Comparison
Thread Solved |
•
•
Join Date: Dec 2008
Posts: 11
Reputation:
Solved Threads: 0
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));
}
} Last edited by ~s.o.s~; Dec 17th, 2008 at 3:00 pm. Reason: Fixed code tags; learn to use them.
•
•
Join Date: Aug 2006
Posts: 137
Reputation:
Solved Threads: 11
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.
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.
•
•
Join Date: Dec 2008
Posts: 11
Reputation:
Solved Threads: 0
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)
•
•
Join Date: Aug 2006
Posts: 137
Reputation:
Solved Threads: 11
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.
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.
•
•
Join Date: Aug 2006
Posts: 137
Reputation:
Solved Threads: 11
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:
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:
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.
Java Syntax (Toggle Plain Text)
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]
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:
java Syntax (Toggle Plain Text)
int comp = 0; for (int k = 0; k <= n - 2; k++) comp += n - 1 - k;
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.
•
•
Join Date: Aug 2006
Posts: 137
Reputation:
Solved Threads: 11
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: You will have:
In that way you'll be counting the number of comparisons. Also, when using the [code] tag please use [code=java].
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:
java Syntax (Toggle Plain Text)
if (values[index] < values[indexOfMin]) indexOfMin = index;
java Syntax (Toggle Plain Text)
if (values[index] < values[indexOfMin]) { indexOfMin = index; count++; }
Last edited by PoovenM; Dec 17th, 2008 at 7:35 pm.
![]() |
Similar Threads
Other Threads in the Java Forum
- Previous Thread: JavaMail Security
- Next Thread: textfiles
| Thread Tools | Search this Thread |
911 actionlistener addressbook android api append applet application array arrays automation binary blackberry block bluetooth character chat class client code component consumer csv database desktop developmenthelp eclipse error fractal ftp game givemetehcodez graphics gui html ide image integer j2me j2seprojects japplet java javaarraylist javac javaee javaprojects jni jpanel julia lego linked linux list loops mac map method methods mobile netbeans newbie number objects online oriented panel printf problem program programming project projects properties recursion replaydirector reporting researchinmotion rotatetext rsa scanner se server set singleton sms sort sql string swing test textfields threads time title tree tutorial-sample ubuntu update windows working






