Selection Sort in Data Structure
Selection sort is another sorting technique in which we find the minimum element in every iteration and place it in the array beginning from the first index. Thus, a selection sort also gets divided into a sorted and unsorted subarray.
What is Selection Sort?
Selection sort has the following characteristics:
- Comparison-based sorting algorithm.
- Inplace sorting technique.
- An unstable sorting algorithm i.e. does not preserve the order of duplicate elements.
- Time complexity is O(n2).
- Selection sort is the best algorithm when swapping is a costly operation.
In every iteration, the selection sort algorithm selects the smallest element from the whole array and swaps it with the leftmost element of the unsorted sub-array.
Steps involved in Selection Sort
1. Find the smallest element in the array and swap it with the first element of the array i.e. a[0].
2. The elements left for sorting are n-1 so far. Find the smallest element in the array from index 1 to n-1 i.e. a[1] to a[n-1] and swap it with a[1].
3. Continue this process for all the elements in the array until we get a sorted list.
Algorithm for Selection Sort
Step 1: For i = 1 to n-1
step 2: Set min = arr[i]
step 3: Set position = i
step 4: For j = i+1 to n-1 repeat:
if (min > arr[j])
Set min = arr[j]
Set position = j
[end of if]
[end of loop]
step 5: swap a[i] with arr[position]
[end of loop]
step 6: END
Pseudo-code for Selection Sort
procedure Selection_sort(int Arr):
for i=0 to length(Arr):
Minimum_element = Arr[0]
for each unsorted element:
if element < Minimum_element
element = New_minimum
swap (Minimum_element, first unsorted position)
end Selection_sort
Working of Selection Sort
Let us understand the working of the selection sort algorithm with the help of the following example:
Consider an array having elements: 40, 10, 35, 15, 20, 2, 10, 7 as shown:
Iteration 1:
Iteration 2:
Iteration 3:
Iteration 4:
Iteration 5:
Iteration 6:
Iteration 7:
Iteration 8:
Thus, the final array after selection sort is:
In this array, we can clearly see that the order of duplicate elements has changed. Thus, selection sort is an unstable algorithm.
Implementation of Selection Sort in C
#include<stdio.h>
int Minimum_element(int[],int,int);
void main ()
{
int Arr[] = {12, 5, 34, 21, 45, 100, 25, 17, 40, 3};
int i,position,temp;
int n = sizeof(Arr[])/sizeof(int);
for(i=0; i<n; i++)
{
position = Minimum_element(Arr, n, i);
temp = Arr[i];
Arr[i]=Arr[position];
Arr[position] = temp;
}
printf("The sorted array is:\n");
for(i=0; i<n; i++)
{
printf("%d ",Arr[i]);
}
}
int Minimum_element(int a[], int n, int i)
{
int min, position, j;
min = a[i];
position = i;
for(j=i+1;j<10;j++)
{
if(a[j] < min)
{
min = a[j];
position = j;
}
}
return position;
}
Selection Sort Implementation in C++
#include<bits/stdc++.h>
using namespace std;
int Minimum_element(int[],int,int);
int main ()
{
int Arr[] = {12, 5, 34, 21, 45, 100, 25, 17, 40, 3};
int i, position, temp;
int n = sizeof(Arr[])/sizeof(int);
for(i=0; i<n ;i++)
{
position = Minimum_element(Arr, n, i);
temp = Arr[i];
Arr[i] = Arr[position];
Arr[position] = temp;
}
cout << "The sorted array is:\n";
for(i=0; i<n; i++)
{
cout << " " << Arr[i];
}
}
int Minimum_element(int a[], int n, int i)
{
int min,position,j;
min = a[i];
position = i;
for(j=i+1; j<10; j++)
{
if(a[j] < min)
{
min = a[j];
position = j;
}
}
return position;
}
Selection Sort Implementation in Java:
public class selectionSort
{
void Selection_sort(int Arr[])
{
int len = Arr.length;
for (int j = 0; j<len-1; j++)
{
int min_position = j;
for (int i = j + 1; i < len; i++)
{
if (Arr[i] < Arr[min_position])
{
min_position = i;
}
}
int temp = Arr[j];
Arr[j] = Arr[min_position];
Arr[min_position] = temp;
}
System.out.println("The sorted Array is: ");
for (int i = 0; i < len; i++)
{
System.out.print(Arr[i] +" ");
}
}
public static void main(String args[])
{
int[] array = {12, 5, 34, 21, 45, 100, 25, 17, 40, 3};
aelectionSort ss = new selectionSort();
ss.Selection_sort(array);
}
}
Implementation of Selection Sort in Python:
def Selection_sort(Arr, length):
for i in range(length):
min_index = i
for j in range(i + 1, length):
if Arr[j] < array[min_index]:
min_index = j
(Arr[i], Arr[min_index]) = (Arr[min_index], Arr[i])
list = [12, 5, 34, 21, 45, 100, 25, 17, 40, 3]
length = len(list)
Selection_sort(list, length)
print('The sorted Array is:')
print(list)
Complexity of Selection Sort
The time complexity of selection sort depends upon comparison as well as swap operation. However, a swap operation is very efficient in the selection sort algorithm as compared to other sorting techniques.
The following table shows the number of comparison operations performed in each iteration:
| Iteration | Number of comparisons |
| 1 | n-1 |
| 2 | n-2 |
| 3 | n-3 |
| . | . |
| . | . |
| . | . |
| n-2 | 2 |
| n-1 | 1 |
Thus, the total number of comparisons are: (n-1) + (n-2) + (n-3)+ ……..+ 1
= n(n-1)/2
~ n2
1. Best Case: In this case, the data is already sorted inside the array. Thus there will be zero number of swaps but the comparison will occur at every point.
2. Average case: Elements are neither in increasing order nor decreasing order. The values in the array are randomly placed.
3. Worst case: In the worst case, the array is completely in decreasing or in the non-increasing order. It will have maximum swaps as well as the maximum number of comparisons.
| Scenario | Time complexity |
| Worst case | O(n2 ) |
| Average case | O(n2 ) |
| Best case | O(n2 ) |
The space complexity of the selection sort algorithm is O(1).
Applications of Selection Sort:
The selection sort technique has the following applications:
- Applicable for smaller datasets.
- Used in those algorithms where the cost of swapping does not matter.
- It cannot work for online data. It needs to have all the array elements for each iteration.
- Best suitable when the cost of writing in flash memory matters.
Conclusion
In this article, we have covered another sorting technique named selection sort. We have covered the characteristics of selection sort which make it different from other sorting techniques.
We have also seen the working of selection sort along with code snippets in different programming languages.