1
\$\begingroup\$

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;
               }
           }

        }
    }
\$\endgroup\$
2
  • 5
    \$\begingroup\$ While it’s true that insertion sort is generally faster, both algorithms are inefficient except on almost-sorted or very small input. I’d therefore like to ask what your use-case is. Maybe another algorithm would be altogether more appropriate. Furthermore, are you aware that Java provides an extremely efficient Arrays.sort implementation? \$\endgroup\$ – Konrad Rudolph May 18 '12 at 10:37
  • 1
    \$\begingroup\$ I am sorting a poker hand from smallest rank to largest, and if the deck is < 5 then inserting a new card, and sorting as needed. I am aware of a few sorting implementation but this is for a class project, and we are not allowed to use any of them. \$\endgroup\$ – user1051043 May 18 '12 at 14:46
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • \$\begingroup\$ I figured out how to change the order of the sort and also made some adjustments to simplify the code a bit. Let me know what you think: \$\endgroup\$ – user1051043 May 19 '12 at 16:48
  • \$\begingroup\$ Yes that code is an insertion sort. Good work. \$\endgroup\$ – pippin1289 May 19 '12 at 23:38
1
\$\begingroup\$

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;
    }
}
\$\endgroup\$
0
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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;
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.