Selection Sort Algorithm

• Selection sort is a very simple sorting algorithm.
• It starts to find out the smallest element by searching in a linear way and swap it with i place and then find the second smallest by searching from n-i elements and place it at ith place and so on.
• It is improved on the performance of bubble sort.
• Complexity in worst case and average case is О(n²) and the worst case is when it is in sorted order.
• It should not be use when n is large.

Example:
An array of sortable elements: {5,3,4,1,2}
Pass 1:

• {5,3,4,1,2} smallest= 5
• {5,3,4,1,2} smallest=3
• {5,3,4,1,2} nothing
• {5,3,4,1,2} smallest=1
• {5,3,4,1,2} nothing
• swap {1,3,4,5,2}

Pass 2:

• {1,3,4,5,2} smallest=3
• {1,3,4,5,2} nothing
• {1,3,4,5,2} nothing
• {1,3,4,5,2} smallest=2
• swap {1,2,4,5,3}

Pass 3:

• {1,2,4,5,3} smallest=4
• {1,2,4,5,3} nothing
• {1,2,4,5,3} smallest=3
• swap {1,2,3,5,4}

Pass 4:

• {1,2,3,5,4} smallest=5
• {1,2,3,5,4} smallest=4
• swap {1,2,3,4,5}

Pseudocode:

   1: procedure SelectionSort( A : list of sortable items ) defined as:

   2: for i ← 0 to length(A)-1

   3:     smallest ← i

   4:     for j ← i+1 to length(A)

   5:         if A[j] < A[smallest]

   6:             smallest = j

   7:     end for    

   8:     swap( A[i], A[smallest] )

   9: end for

  10: end procedure

Implementation in C#:

   1: public int[] SelectionSort(int[] array)

   2:         {

   3:             int smallest, temp;

   4:             for (int i = 0; i < array.Length - 1; i++)

   5:             {

   6:                 smallest = i;

   7:                 for (int j = i + 1; j < array.Length; j++)

   8:                 {

   9:                     if (array[j] < array[smallest])

  10:                         smallest = j;

  11:                 }

  12:                 temp = array[i];

  13:                 array[i] = array[smallest];

  14:                 array[smallest] = temp;

  15:             }

  16:             return array;

  17:         }

Tags: Selection Sort, Algorithm, Sorting

Good Luck