Insertion vs Selection

Question

I currently have a selection sorting algorithm, but need some help turning it into a insertion sort, I understand a insertion sort if faster? The hand array is full, and it needs to sort from lowest to highest rank.

private void sort(PlayingCard[] hand)
    {
        PlayingCard temp;
        for(int i = 0; i < hand.length ; i++) 
        {

           for(int j = i+1; j < hand.length ; j++)
           {
               int compareRank = hand[j].getRank().compareTo(hand[i].getRank());

               if(compareRank < 0){
                   temp = hand[i];
                   hand[i] = hand[j];
                   hand[j] = temp;
               }
           }

        }
    }

Answer 1

So there are a few ways of making this into an insertion sort. One way would be similar to the following code (which is adapted from the pseudo code on wikipedia):

//insert each item into the sorted part of the list
for(int i = 1; i<hand.length(); i++){
  //make sure to save a temporary
  PlayingCard card = hand[i];
  int j = i;
  //now we search through the already sorted part 
  //of the list looking for insertion point
  while(j > 0 && hand[j-1].getRank().compareTo(card.getRank()) < 0){ //make sure comparator is correct
    //we know item is less than hand[j-1]. so we need to move it to hand[j]  
    hand[j] = hand[j-1];
    j -= 1;
  }
  //now we insert j
  hand[j] = card;
}

Now this is not the most efficient way of implementing an insertion sort, but rather one of the simplest. I will let you ponder on ways to improve this. One thing to think about is how to more quickly find the insertion point. As in we can use a binary search to find the insertion point (meaning less comparisons are taking place). Other items that can be done, though this is much more difficult, is to regulate the amount of swaps (probably beyond your course). Work with this code and the data structures to see what you come up with. Good luck!

Answer 2

Here is a sort that I put together after some research:

private void sort(PlayingCard[] hand)
{
    int i, j;
    PlayingCard temp;    
    for (i = 1; i < hand.length; i++) {
        temp = hand[i];
        j = i;
        while (j > 0 && hand[j - 1].getRank().compareTo(temp.getRank()) > 0) {
            hand[j] = hand[j - 1];
            j--;
        }        
        hand[j] = temp;
    }
}

Answer 3

There are only 120 possible permutations of five items; if one starts by ordering items 1 and 2, and items 3 and 4, that will leave 30 permutations, which can then be sorted using five more comparisons. If you're worried about speed, use explicit operations on the five items rather than using loops.

Answer 4

Two small notes about the original code:

1. About the temp variable: try to minimize the scope of local variables. It's not necessary to declare them at the beginning of the method, declare them where they are first used. (Effective Java, Second Edition, Item 45: Minimize the scope of local variables)

2. Furthermore,

   temp = hand[i];
   hand[i] = hand[j];
   hand[j] = temp;
   

   could be extracted out to a swap method:

   public void swap(final PlayingCard[] arr, final int pos1, final int pos2) {
       final PlayingCard temp = arr[pos1];
       arr[pos1] = arr[pos2];
       arr[pos2] = temp;
   }