Q. Give the algorithm for the selection sort. Describe the behaviours of selection sort when the input given is already sorted.
Ans.
Algorithm for the Selection Sort is as follows
SELECTION (A, N)
This algorithm sorts the given array A with N elements
1. Repeat steps 2 & 3 for K = 1,2........N-1
2. Call MIN (A,K, N, LOC)
3. [Interchange A[K] and A[LOC].]
Set TEMP : = A[K], A[K]:=A[LOC] and A[LOC]: = TEMP, [END of Step 1 loop]
4. EXIT
MIN (A, K, N, LOC)
An array A is in memory. This procedure finds the location LOC of the smallest element among A[K], A[K+1]...........A[N],
1. Set MIN : =A[K] and LOC:=K [Initialize pointer]
2. Repeat for J= K+1, K+2, .....N;
If MIN > A[J], then : set MIN: = A[J] and LOC:=J [End of loop]
3. Return
The complexities of Selection sort are given below
|
Worst Case
|
Average Case
|
Best Case
|
|
O(n2)
|
O(n2)
|
O(n2)
|
So if the list is already sorted the it is the best case, then also the complexity of algorithm is O(n2). Therefore, there is no change in behaviors of selection sort if the list is already sorted.