Sorting Algorithms - Part I

Selection Sorting

Algorithm

for i = 1:n,
    k = i
    for j = i+1:n, if a[j] < a[k], k = j
    → invariant: a[k] smallest of a[i..n]
    swap a[i,k]
    → invariant: a[1..i] in final position
end

Implementation in Java

public static void selectionSorting(int[] arr){  
  for(int i=0;i<arr.length;i++){
   int k =i;
   for(int j=i+1;j<arr.length;j++){
    if(arr[j]<arr[k]){
     k=j;
    }
   }
   int temp=arr[k];
   arr[k]=arr[i];
   arr[i]=temp;
  }  
 }

Properties

• O(1) extra space
• O(n²) comparisons
• O(n) swaps

Usage

This algorithms has O(n²) comparisons property so run time is always quadratic. So selection sort is not an algorithm that we don't want to use.
Interesting property is it minimizes the number of swaps. There for it can be used in sorting where swapping costs  high.