Selection Sort
The Selection sort algorithm is based on the idea of finding the minimum or maximum element in an unsorted array and then putting it in its correct position in a sorted array.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
It is repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.
- The algorithm maintains two subarrays in a given array.
2) Remaining subarray which is unsorted.
0 1 2 3 //Index
7 4 5 2 // Values
Step 1: set i, min=0 location and j=1st location
min / i= 0 j= 1 2 3
7 4 5 2
Step 2: for i in N: set min=i ie min=0
Step 3: for j in N:
compare arr[ j ]< arr[ min ] ie arr[ 1 ]< arr[0] 4<7
If yes, min=j min=1
Step 4: repeat to step 3
compare arr[ j ]< arr[ min ] ie arr[ 2 ]< arr[1] 5<4
If yes, min=j
compare arr[ j ]<arr[min] arr[3] < arr[1] 2<4
If yes, min =j min=3Step 5: Swap the elements arr[i], arr[min] = arr[min], arr[i] i= 0 j=1 2 min= 3
2 4 5 7
Step 6: Repeat step 2 and 3 from min=i
sorted i/ min = 1 j=2 3
2 4 5 7
compare arr[ j ]< arr[ min ] ie arr[2]< arr[1] 5<4
If yes, k=min k=1
compare arr[ j ]<arr[min] arr[3] < arr[1] 7<4
If yes, k =min
sorted i/ min = 1 2 j= 3
2 4 5 7
Worst Case Complexity: O(n2)
If we want to sort in ascending order and the array is in descending order
then, the worst case occurs.
Best Case Complexity: O(n2)
It occurs when the array is already sorted
Average Case Complexity: O(n2)
It occurs when the elements of the array are in jumbled order (neither
ascending nor descending)
No comments