Selection sort is a comparison-based sorting technique in which the minimum or the maximum element (according to the sorting order i.e. ascending or descending order respectively) are found out from the unsorted array and are placed at its proper sorted position after each pass. From the next pass, that element is not considered again in the sorting. The sorting takes place from the next element of the array. In this technique, after 1st pass, the array gets divided into two parts. One is the sorted part and another is the unsorted part. It is an in-place sorting algorithm as it does not require any extra space for sorting.
PROCEDURE WITH EXAMPLE:
In the case of selection sort if the number of elements is n then n - 1 passes are required to sort the elements of the array which is similar to the bubble sort. For example, if we consider the unsorted array as follows with 5 elements then we will need 5 - 1= 4 passes to sort the data (in ascending order).
In the first pass, it is considered that the minimum element is -7 and also the first index is considered as the index of the minimum element of the array (i.e. 0). -7 will be compared with 54. But as -7 is lesser than 54 so there will be no change in the min value. After that -7 will be compared with -9. As -9 is lesser than -7 so the min value will be changed to -9 and the index of the minimum element will be changed to 2. Now, -9 is compared with 76 and 23 but in both cases, -9 is smaller so there will be no change.
After completing this pass we will get the minimum element -9 and the index 2 which will be swapped with the first element of the array and the after the first pass the array will be:
-9 is now placed in its sorted position.
In the second pass, the 1st element will not be taken in the sorting, the 2nd element i.e. 54 will be considered as the minimum element for the first time and the index will be stored as 1. Now, in a similar way to the 1st pass, it will be compared the rest of the elements of the array and in this pass, -7 will be found as the minimum element whose index is 2. So in this pass, the element 54 will be swapped with -7 and the array after swapping will be:
In the third pass, the third element of the array is considered as the minimum element in this case which is again 54 but here the index value is 2. Now 54 is compared with 76 but as 54 is lesser than 76 so there will be no change in the minimum value, after that 54 is again compared to the last element 23. As 23 is lesser than 54, so the minimum value will be changed to 23 and the index will be 4.
Now 23 is swapped with 54 and we will get the array:
This is the last pass of the sorting technique. Only two elements are left to be sorted. For this pass, element 76 is considered as the minimum element and the index is 3. Now 76 will be compared with 54, in this case, 54 is less than 76 so the minimum value will be 54 and the index value is 4 which will be swapped with 76. After this swapping we will get the final sorted array as follows:
INPUT:An unsorted array a[6,2,4,1,…………….,n] OUTPUT:An sorted array a[1,2,3,4,5,…………..,n] (in ascending order) PROCESS: Step 1: [Taking the number of elements from the user] Read n Step 2: [Take the unsorted elements from the user in an array] For i=0 to n Read arr[i] Step 3: [Print the unsorted array] For i=0 to n Print arr[i] Step 4:[Sorting the unsorted elements] For i=0 to i<n repeat Set min<-a[i] Set pos<-i For j=i+1 to j<n If(a[j]<min) then Set min<-a[j] Set pos<-j [End of inner ‘For’ loop] Set ta[i] Set a[i]<-a[pos] Set a[pos]<-t [End of outer ‘For’ loop] Step 5: [Printing the sorted array] For i=0 to n Print arr[i] Step 6: Stop.
1. It is a comparison-based sorting technique.
2. It is an in-place sorting.
3. The array is divided into two parts while sorting, the left part is the sorted part and the right part is the unsorted part.
4. It cannot work efficiently for a large amount of data.
1. It is used when the memory cost does not matter.
2. It is used to sort a small amount of data.
1. It works efficiently on a small amount of data.
2. It is an in-place sorting algorithm and space complexity is O(1).
3. It is very easy and simple to understand.
4. The sorting does not depend on the initial arrangement of the array elements before sorting
1. It cannot work efficiently for a large number of elements.
2. Its performance is worse than insertion sort.
3. It is not a stable algorithm.
For this above algorithm the best case, average case, and the worst-case time complexity of selection sort will be the same.
For n number of elements the number of comparisons in the first pass is n - 1, in the second pass n - 2, and so on, and in the last pass the number of comparisons is 1 as explained earlier through example.
Therefore for n number of elements, the total number of comparisons to sort the array is:
The space complexity of this algorithm is O(1) as it is an in-place algorithm and it does not require any extra space for performing the sorting.