Selection Sorting Algorithm, Time Complexity of Selection Sort

Explain Selection Sorting Algorithm, Time Complexity of Selection Sort with Example


Find smallest element and put it in a[1].

Find 2nd smallest element and put it in a[2].

etc. Less data movement (no bubbling)

Pseudocode:
   

for (int i = 1; i < n; i++) {
      find minimum element a[min] in             subseqeunce a[1..n]
      exchange a[min] and a[i]
    }


After iteration i, a[1] ... a[i] are in final position.


Time Complexity of Selection Sort

for (int i = 1; i < n; i++) {
    int min = i;
    for (int j = i + 1; j <= n; j++) {
       if (a[j] < a[min]) {
         min = j;
       }
    }
    temp = a[min];
    a[min] = a[i];
    a[i] = temp;
}
Worst Case Analysis
Most executed instruction are those in inner for loop (if)

Each such instruction is executed (N-1) + (N-2) + ... + 2 + 1 times

Time complexity: O(N2)



Labels: