Selection Sort Method + Comparison

Thread Solved

Join Date: Dec 2008
Posts: 11
Reputation: javafrustrated is an unknown quantity at this point 
Solved Threads: 0
javafrustrated javafrustrated is offline Offline
Newbie Poster

Selection Sort Method + Comparison

 
0
  #1
Dec 17th, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Aug 2006
Posts: 137
Reputation: PoovenM is on a distinguished road 
Solved Threads: 11
PoovenM PoovenM is offline Offline
Junior Poster

Re: Selection Sort Method + Comparison

 
0
  #2
Dec 17th, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 11
Reputation: javafrustrated is an unknown quantity at this point 
Solved Threads: 0
javafrustrated javafrustrated is offline Offline
Newbie Poster

Re: Selection Sort Method + Comparison

 
0
  #3
Dec 17th, 2008
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)
Reply With Quote Quick reply to this message  
Join Date: Aug 2006
Posts: 137
Reputation: PoovenM is on a distinguished road 
Solved Threads: 11
PoovenM PoovenM is offline Offline
Junior Poster

Re: Selection Sort Method + Comparison

 
0
  #4
Dec 17th, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 11
Reputation: javafrustrated is an unknown quantity at this point 
Solved Threads: 0
javafrustrated javafrustrated is offline Offline
Newbie Poster

Re: Selection Sort Method + Comparison

 
0
  #5
Dec 17th, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Aug 2006
Posts: 137
Reputation: PoovenM is on a distinguished road 
Solved Threads: 11
PoovenM PoovenM is offline Offline
Junior Poster

Re: Selection Sort Method + Comparison

 
0
  #6
Dec 17th, 2008
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:
  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:
  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.
Reply With Quote Quick reply to this message  
Join Date: Dec 2008
Posts: 11
Reputation: javafrustrated is an unknown quantity at this point 
Solved Threads: 0
javafrustrated javafrustrated is offline Offline
Newbie Poster

Re: Selection Sort Method + Comparison

 
0
  #7
Dec 17th, 2008
I think I might just give up on this one. The assignment can't we worth that much.

thanks for trying to help.
Reply With Quote Quick reply to this message  
Join Date: May 2007
Posts: 4,438
Reputation: Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of 
Solved Threads: 510
Moderator
Featured Poster
Ezzaral's Avatar
Ezzaral Ezzaral is offline Offline
Industrious Poster

Re: Selection Sort Method + Comparison

 
0
  #8
Dec 17th, 2008
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.
Reply With Quote Quick reply to this message  
Join Date: Aug 2006
Posts: 137
Reputation: PoovenM is on a distinguished road 
Solved Threads: 11
PoovenM PoovenM is offline Offline
Junior Poster

Re: Selection Sort Method + Comparison

 
0
  #9
Dec 17th, 2008
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:
  1. if (values[index] < values[indexOfMin])
  2. indexOfMin = index;
You will have:
  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.
Reply With Quote Quick reply to this message  
Join Date: May 2007
Posts: 4,438
Reputation: Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of Ezzaral has much to be proud of 
Solved Threads: 510
Moderator
Featured Poster
Ezzaral's Avatar
Ezzaral Ezzaral is offline Offline
Industrious Poster

Re: Selection Sort Method + Comparison

 
0
  #10
Dec 17th, 2008
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 .
Reply With Quote Quick reply to this message  
Reply

This thread has been marked solved.
Perhaps start a new thread instead?
Message:



Similar Threads
Other Threads in the Java Forum
Thread Tools Search this Thread



About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC