943,696 Members | Top Members by Rank

Ad:
  • Java Discussion Thread
  • Marked Solved
  • Views: 3063
  • Java RSS
You are currently viewing page 1 of this multi-page discussion thread
Dec 17th, 2008
0

Selection Sort Method + Comparison

Expand Post »
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.
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
javafrustrated is offline Offline
11 posts
since Dec 2008
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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.
Reputation Points: 56
Solved Threads: 11
Junior Poster
PoovenM is offline Offline
147 posts
since Aug 2006
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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)
Reputation Points: 10
Solved Threads: 0
Newbie Poster
javafrustrated is offline Offline
11 posts
since Dec 2008
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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.
Reputation Points: 56
Solved Threads: 11
Junior Poster
PoovenM is offline Offline
147 posts
since Aug 2006
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
javafrustrated is offline Offline
11 posts
since Dec 2008
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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:
Java Syntax (Toggle Plain Text)
  1. for i ← 0 to n-2 do
  2. min ← i
  3. for j ← (i + 1) to n-1 do
  4. if A[j] < A[min] //this is the comparison
  5. min ← j
  6. 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:
java Syntax (Toggle Plain Text)
  1. int comp = 0;
  2. for (int k = 0; k <= n - 2; k++)
  3. 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.
Reputation Points: 56
Solved Threads: 11
Junior Poster
PoovenM is offline Offline
147 posts
since Aug 2006
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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

thanks for trying to help.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
javafrustrated is offline Offline
11 posts
since Dec 2008
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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.
Moderator
Featured Poster
Reputation Points: 3239
Solved Threads: 838
Posting Genius
Ezzaral is offline Offline
6,757 posts
since May 2007
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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:
java Syntax (Toggle Plain Text)
  1. if (values[index] < values[indexOfMin])
  2. indexOfMin = index;
You will have:
java Syntax (Toggle Plain Text)
  1. if (values[index] < values[indexOfMin])
  2. {
  3. indexOfMin = index;
  4. count++;
  5. }
In that way you'll be counting the number of comparisons. Also, when using the [code] tag please use [code=java].
Last edited by PoovenM; Dec 17th, 2008 at 7:35 pm.
Reputation Points: 56
Solved Threads: 11
Junior Poster
PoovenM is offline Offline
147 posts
since Aug 2006
Dec 17th, 2008
0

Re: Selection Sort Method + Comparison

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 .
Moderator
Featured Poster
Reputation Points: 3239
Solved Threads: 838
Posting Genius
Ezzaral is offline Offline
6,757 posts
since May 2007

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Java Forum Timeline: JavaMail Security
Next Thread in Java Forum Timeline: textfiles





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC