Wednesday, June 12, 2013

Selection Sort Algorithm in Java

Selection sort is a in-place sorting algorithm. Works well small files.It starts by comparing the entire list for the lowest item and moves it to the #1 position. It then compares the rest of the list for the next-lowest item and places it in the #2 position and so on until all items are in the required order.

Steps to perform selection sort
  1. Get a hand of unsorted card.
  2. Set a marker for unsorted section at the front of hand
  3. Repeat 4 to 7 steps until one card is left in the unsorted selection
  4. Compare all unsorted card
  5. Select the smallest unsorted card
  6. Swap this card with the first card in the unsorted section
  7. Move the marker.
  8. Stop

Let take a deck of unsorted card (step 1).
7 8 5 2 4 6 3 
Now set a marker at the front of unsorted card (step 2).
|7 8 5 2 4 6 3

Compare all the card from 7 to 3 (step)
Find the smallest shorted card (step 4) i.e., 2
So we swap this card with the first unsorted card i.e., 2 is swap with 7
|2 8 5 7 4 6 3 
Move the marker (step 8)
2|8 5 7 4 6 3 

Similarly, we repeat the step
Find the smallest unsorted card i.e., 3 and replace with first unsorted card 8
2|3 5 7 4 6 8
Move the marker
2 3|5 7 4 6 8

Find the smallest unsorted card i.e., 4 and replace with first unsorted card 5
2 3|4 7 5 6 8
Move the marker
2 3 4|7 5 6 8

Find the smallest unsorted card i.e., 5 and replace with first unsorted card 7
2 3 4|5 7 6 8
Move the marker
2 3 4 5|7 6 8

Find the smallest unsorted card i.e., 6 and replace with first unsorted card 7
2 3 4 5
|6 7 8
Move the marker
2 3 4 5 6|7 8

Find the smallest unsorted card i.e., 7 and replace with first unsorted card 7
2 3 4 5 6|7 8
Move the marker
2 3 4 5 6 7|8

Now we have one unsorted card means algorithm is complete.

Demo:



Performance :
  • Worst Case Complexity : O(n^2)
  • Average Case ComplexityO(n^2) 
  • Best Case Complexity : O(n^2)


If you know anyone who has started learning Java, why not help them out! Just share this post with them. 
Thanks for studying today!...

1 comment:

  1. Hey.. Entire code is erfect. The only things that can be added here to escape from unwanted swap for same element, i.e., don't need to do swapping when no element is found


    static int[] selectionSort( int[] array){

    System.out.println("array.length="+ array.length);

    for (int i = 0; i < array.length - 1; i++) {
    System.out.println("******************");
    boolean flag = false;

    int pos = i;
    for (int j = i+1; j < array.length; j++) {

    if( array[pos] > array[j]){
    pos = j;
    flag = true;
    }
    }


    if( flag ){
    int temp = array[i];
    array[i] = array[pos];
    array[pos] = temp;

    }

    System.out.println(Arrays.toString(array));
    }

    return array;
    }

    ReplyDelete