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: Data Structure