Selection sort

  • (2 Pages)
  • +
  • 1
  • 2

21 Replies - 2538 Views - Last Post: 07 March 2011 - 08:29 PM Rate Topic: -----

#1 johnathanc456   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 05-May 10

Selection sort

Posted 05 March 2011 - 05:15 PM

I have an array of worker objects that need to be sorted. there are two different methods the sortbyName() and sortbyHoursWorked() i am working on Hours worked at the moment and am having some issues getting it to compile. Being as the worker objects get a string name and an int hoursworked there are multiple types involved. in my case i am getting incompatable types where it is wxpecting a worked but an int is being passed in. Any ideas on what i could change to fix this. the error is on line 40
	wa[outsideIndex] = temp;  


Any help is greatly appreciated.
Thanks

Here is my entire code for the binary sorting and searching as well as the worker class:
public class Lab8
{ Worker[] wa = new Worker[5];
	public Lab8()
	{
	}
	public Worker[] sortByName(Worker[] wa)
	{//Sorts the input array by the name stored in each object. 
	//This is a case-sensitive lexicographic order sort, so Jimbob is different than jimbob. 
	//The former sorts before the latter. All objects provide a getName() method
		
	
	return wa;
	}
	
	public Worker[] sortByHoursWorked(Worker[] wa)
	{//Sorts the input array by the number of hours worked stored in each object.
	//all objects provide a getHoursWorked() method
	//selection sort
			int min, temp;
		//walks the array
		for (int outsideIndex = 0; outsideIndex < wa.length-1; outsideIndex++)
		{
			min = outsideIndex;
			for (int insideIndex = outsideIndex+1; insideIndex < wa.length; insideIndex++)
				if (wa[insideIndex].getHoursWorked() < (wa[min].getHoursWorked())){
					min = insideIndex;
				}
			// Swap the values
			temp = wa[min].getHoursWorked();
			wa[min] = wa[outsideIndex];
			wa[outsideIndex] = temp;
		}
 		return wa;
	}
	
	public Worker binarySearch(Worker[] wa, String target)
	{//Searches for an object whose name is the same as the given string argument.
	//Note: This method must be a binary search -- using a linear search will penalize you the 5 points between 95 and 100 that I normally award. 
	int lowestPossibleLoc = 0;
	    int highestPossibleLoc = wa.length - 1;
	    
	    while (highestPossibleLoc >= lowestPossibleLoc) {
	       int middle = (lowestPossibleLoc + highestPossibleLoc) / 2;
	       if (wa[middle].getName().equals(target)) {
	                 //target has been found at this index!
	          return wa[middle];
	       }
	       else if (wa[middle].getName().compareTo(target) > 0) {
	                 // eliminate locations >= middle
	          highestPossibleLoc = middle - 1;
	       }
	       else {
	                 // eliminate locations <= middle
	          lowestPossibleLoc = middle + 1;   
	       }
					  return wa[middle];

	    }
	    
	    // At this point, highestPossibleLoc < LowestPossibleLoc,
	    // which means that N is known to be not in the array.  Return
	    // a -1 to indicate that N could not be found in the array.
	 
	  	return wa[-(lowestPossibleLoc + 1)]; 
		}
}




Worker class:
public class Worker
{
	private String name;
	private int unitsWorked;

	/**
	 * Initializes a Worker object
	 * @param s Name of this person
	 */
	public Worker(String s)
	{
		 name = s;
		 unitsWorked = 0;
	}
	
	public int work(int units)
	{
		if (units >= 0)
			unitsWorked += units;
		return unitsWorked;
	}
	
	public String getName()
	{
	
	return name;
	}
	

	public int getHoursWorked()
	{
	
	return unitsWorked;
	}

	/**
	 * @return string that represents this Worker object
	 */
	public String toString()
	{
		return super.toString() + " name: " + 	this.name + 
			", unitsWorked: " + unitsWorked;
	}
}





Is This A Good Question/Topic? 1
  • +

Replies To: Selection sort

#2 baavgai   User is online

  • Dreaming Coder
  • member icon


Reputation: 7164
  • View blog
  • Posts: 14,932
  • Joined: 16-October 07

Re: Selection sort

Posted 05 March 2011 - 07:33 PM

Your array is of type Worker. So you temp must be as well. The element you used for comparison has nothing to do with the swap.

Worker temp = wa[min];
wa[min] = wa[outsideIndex];
wa[outsideIndex] = temp;


Was This Post Helpful? 0
  • +
  • -

#3 johnathanc456   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 05-May 10

Re: Selection sort

Posted 05 March 2011 - 07:40 PM

OK, i see what is wrong now, because after the comparison is done the swap doesn't need to know what the name was it just takes in my case the whole worker and swaps positions.

Thanks.
Was This Post Helpful? 0
  • +
  • -

#4 johnathanc456   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 05-May 10

Re: Selection sort

Posted 06 March 2011 - 02:56 PM

When i attempt to sort by name it doesn't work, as far as i can tell the code is correct. would it be better to use a n insertion sort instead of selection sort in this case?
Any feedback is greatly appreciated.
Here is my code for sorting by name:

	public Worker[] sortByName(Worker[] wa)
	{//Sorts the input array by the name stored in each object. 
	//This is a case-sensitive lexicographic order sort, so Jimbob is different than jimbob. 
	//The former sorts before the latter. All objects provide a getName() method
	int min;
	Worker temp;//temperaryly holding the String to be moved / Swapped
		//walks the array
		for (int outsideIndex = 0; outsideIndex < wa.length-1; outsideIndex++)
		{
			min = outsideIndex;
			for (int insideIndex = outsideIndex+1; insideIndex < wa.length; insideIndex++)
				if (wa[insideIndex].getName().equals(wa[min].getName())){
					min = insideIndex;
				}
			// Swap the values
			temp = wa[min];
			wa[min] = wa[outsideIndex];
			wa[outsideIndex] = temp;
		}
	
	
	return wa;
	}




Was This Post Helpful? 0
  • +
  • -

#5 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Selection sort

Posted 06 March 2011 - 03:06 PM

You systematically swap the object what ever they are
You have to swap only if required
Your swap code is outside the if()
Was This Post Helpful? 1
  • +
  • -

#6 baavgai   User is online

  • Dreaming Coder
  • member icon


Reputation: 7164
  • View blog
  • Posts: 14,932
  • Joined: 16-October 07

Re: Selection sort

Posted 06 March 2011 - 03:17 PM

For sorting, you want compareTo. That will allow you to figure out which is less or greater. I'm not entirely how you'd sort with just equals.
Was This Post Helpful? 1
  • +
  • -

#7 johnathanc456   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 05-May 10

Re: Selection sort

Posted 06 March 2011 - 04:19 PM

I have changed line 12 and put the swap into the if statement it now looks like this:
for (int insideIndex = outsideIndex+1; insideIndex < wa.length; insideIndex++)
				if (wa[insideIndex].getName().compareTo(wa[min].getName()) > 0){
					min = insideIndex;
				
				// Swap the values
				temp = wa[min];
				wa[min] = wa[outsideIndex];
				wa[outsideIndex] = temp;
				}



but i'm just wondering, would an insertion sort be better suited for this scenario? there are 10 workers at the most.
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12305
  • View blog
  • Posts: 45,401
  • Joined: 27-December 08

Re: Selection sort

Posted 06 March 2011 - 04:24 PM

Quicksort is still the most efficient sorting algorithm for arrays. That's why the Arrays.sort() method uses it. Insertion Sort is more efficient than Selection Sort in all cases, and right on par with Mergesort for small arrays like you have here.
Was This Post Helpful? 0
  • +
  • -

#9 pbl   User is offline

  • There is nothing you can't do with a JTable
  • member icon

Reputation: 8378
  • View blog
  • Posts: 31,956
  • Joined: 06-March 08

Re: Selection sort

Posted 06 March 2011 - 05:16 PM

Worry with efficiency wehen you will have 25,000 to 100,000 Workers to sort.
Right now, the clearer and simplest algorithm (or the one you are more confortable with) should do the job
Was This Post Helpful? 1
  • +
  • -

#10 johnathanc456   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 05-May 10

Re: Selection sort

Posted 06 March 2011 - 05:41 PM

Alright, i decided to keep it a selection sort. Now when i want to search the names it works correctly except for when there is no name that matches the search in the array, it is supposed to return -1 but instead throws a array out of bounds exception. i can see why it does this because I'm trying to return an object at wa[-1] instead of returning -1. But when i attempt "return -1;" it doesn't work because the return types don't match. it requires a worker and I'm trying to return an int. any suggestions as to how i can get it to return -1?

here is the binary search code:
	public Worker binarySearch(Worker[] wa, String target)
	{//Searches for an object whose name is the same as the given string argument.
	//Note: This method must be a binary search -- using a linear search will penalize you the 5 points between 95 and 100 that I normally award. 
	int lowestPossibleLoc = 0;
	    int highestPossibleLoc = wa.length - 1;
	    while (highestPossibleLoc >= lowestPossibleLoc) {
	       int middle = (lowestPossibleLoc + highestPossibleLoc) / 2;
	   	if (wa[middle] != null){    
			 if (wa[middle].getName().equals(target)) {
	                 //target has been found at this index!
	          return wa[middle];
	       }
	       else if (wa[middle].getName().compareTo(target) > 0) {
	                 // eliminate locations >= middle
	          highestPossibleLoc = middle - 1;
	       }
	       else {
	                 // eliminate locations <= middle
	          lowestPossibleLoc = middle + 1;   
	       }
	    }
		 }
	    
	    // At this point, highestPossibleLoc < LowestPossibleLoc,
	    // which means that the Name is known to be not in the array.  Return
	    // a -1 to indicate that the Name could not be found in the array.
	 
	  	return wa[-(lowestPossibleLoc + 1)]; //returns wa[-1] instead of -1 throwing an arrayoutofbounds Exception
		}



Was This Post Helpful? 0
  • +
  • -

#11 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12305
  • View blog
  • Posts: 45,401
  • Joined: 27-December 08

Re: Selection sort

Posted 06 March 2011 - 06:05 PM

This is a poor design. You are using an array, which has constant-time random access of elements. That means if your binarySearch() method returns an int isntead of a Worker (change the method return type), accessing the element in the array outside of the method takes practically no time. You cannot return a Worker or an int (ok, you can change the return type of the method to Object, but you are playing with fire here. I would not want to maintain that code.). You should return either a Worker and let your method throw an Exception, or preferably return an int as almost every other binarySearch() method does. Or another option is to return null if the element is not found.
Was This Post Helpful? 0
  • +
  • -

#12 johnathanc456   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 05-May 10

Re: Selection sort

Posted 06 March 2011 - 06:26 PM

I changed it to return null, and now it works fine. I now have to 1)sort array containing null elements by hoursWorked. 2)sort array containing null elements by name. 3)sort array containing null elements & null names by name. any pointers/ links on how i might go about doing this?
Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12305
  • View blog
  • Posts: 45,401
  • Joined: 27-December 08

Re: Selection sort

Posted 06 March 2011 - 06:36 PM

I would just move elements with null names to the front of the list, and null elements to the back of the List. This makes sense b/c a null name/no name comes before the letter A logically. And we don't care about null elements, so let's just move them to the end of the List.
Was This Post Helpful? 1
  • +
  • -

#14 johnathanc456   User is offline

  • D.I.C Head

Reputation: 2
  • View blog
  • Posts: 53
  • Joined: 05-May 10

Re: Selection sort

Posted 06 March 2011 - 07:03 PM

ok I see how that would work, how might i go about sorting those elements around? would it be a simple as an if/else statement?
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12305
  • View blog
  • Posts: 45,401
  • Joined: 27-December 08

Re: Selection sort

Posted 06 March 2011 - 07:03 PM

Yes. There is no reason you can't treat nulls as normal elements.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2