## Monday, September 29, 2008

### 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