Cheater Catcher Lab

<< Card Class Lab 2: Poker Hands | LabTrailIndex | Cryptography Lab >>

What type of sort method is needed and where should it go?

Any of the sort methods we've learned so far will work, but Selection Sort would be easiest.

You have to ensure that it's been adapted for an array list of the type ScoreRecord when you're comparing the pieces of the array list, you have to extract from each record the score, and compare them to correctly order them.

For instance

 public ArrayList<ScoreRecord> sort( ArrayList<ScoreRecord> list);
 {
       ...stuff...

          ScoreRecord sr=list.get(i);
         int theScore=sr.getScore();
         ...more stuff ....
}

MergeSort Example:

There are two parts to the Merge sort algorithm.. the spliting part (here called "mergeSort") and the merging part (here called "merge")

The idea of the splitting part is to split the list into two halves, and then split those parts into two halves, and so on, until there is only one thing in the split list.

Then the merge stage begins. looking at the left and right lists, pick the side that is first, and remove it from that side... when there is nothing left, what you have is sorted. This is efficient, but difficult to do from memory unless you have done it a few times. The Selection sort algorithm is easier to code and is only slightly less efficient.

	public static ArrayList<ScoreRecord> mergeSort(ArrayList<ScoreRecord> s) {
		if (s.size() <= 1)
			return s;

		int middle = s.size() / 2;
		ArrayList<ScoreRecord> left = new ArrayList<ScoreRecord>();
		ArrayList<ScoreRecord> right = new ArrayList<ScoreRecord>();
		for (int i = 0; i < middle; i++) {
			left.add(s.get(i));
		}
		for (int i = middle; i < s.size(); i++) {
			right.add(s.get(i));
		}

		left =mergeSort(left);
		right=mergeSort(right);
		ArrayList<ScoreRecord> result=merge(left,right);

		return result;

	}

	public static ArrayList<ScoreRecord> merge(ArrayList<ScoreRecord> left, ArrayList<ScoreRecord> right)
	{
		ArrayList<ScoreRecord> result = new ArrayList<ScoreRecord>();
		while (left.size()>0 && right.size()>0)
		{
			if (left.get(0).getScore() >= right.get(0).getScore()){
				result.add(left.get(0));
			    left.remove(0);
			}else {
				result.add(right.get(0));
				right.remove(0);
			}
		}
		//Since left or right ran out, we attach the remainder to the result
		while (left.size()>0) 
		{
			result.add(left.get(0));
			left.remove(0);
		}
		while (right.size()>0)
		{
			result.add(right.get(0));
			right.remove(0);
		}
		return result;
	}
}

Selection Sort

The algorithm works as follows:

1. Find the maximum value in the list
2. Swap it with the value in the first position
3. Repeat the steps above for remainder of the list (starting at the second position)

public static ArrayList<ScoreRecord> sort( ArrayList<ScoreRecord> list )
	{

               for (int i=0; i< list.size()-1; i++ ) 
		{
		     int largest=i; //presume this is the largest
                     //  now check if anything to the right is larger still....
                     for (int j=i+1; j< list.size(); j++)
                     {
                        if (list.get(j).getScore() > list.get(largest).getScore()){
				largest=j;			   
		     }
                   //swap the ScoreRecord in the i-th position for the largest
                   ScoreRecord buffy=list.get(i);
                   list.set(i, list.get(largest));
                   list.set(largest, buffy);
		}

		return list;
	}

<< Card Class Lab 2: Poker Hands | LabTrailIndex | Cryptography Lab >>