Selection sort is a simple sorting algorithm. It sorts an array by 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.
1) The subarray which is already sorted.
2) Remaining subarray which is unsorted.
Initially, the sorted part is empty and the unsorted part is the entire list.
In every iteration of selection sort, the minimum element (considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.
How Selection Sort Works?
arr[] = 66 24 16 20 17 // Find the minimum element in arr[0...4] // and place it at beginning 16 24 66 20 17 // Find the minimum element in arr[1...4] // and place it at beginning of arr[1...4] 16 17 66 20 24 // Find the minimum element in arr[2...4] // and place it at beginning of arr[2...4] 16 17 20 66 24 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 16 17 20 24 66
Algorithm
- Step 1 − Set SMALL to location 0
- Step 2 − Search the minimum element in the list
- Step 3 − Swap with value at location SMALL
- Step 4 − Increment SMALL to point to next element
- Step 5 − Repeat until list is sorted
Let’s take a look at the implementation.
public class Sort {
public static void selectionSort(int arr[],int small,int pos) {
int temp;
for(int i=0;i<=arr.length-2;i++)
//set current element as minimum or small
{
small = arr[i];
pos = i;
for(int j=i+1;j<=arr.length-1;j++)
{
//check the element to be small
if(arr[j]<small){
small = arr[j];
pos = j;
}
}
//swap the minimum element with the current element
temp=arr[i];
arr[i]=arr[pos];
arr[pos]=temp;
}
}
public static void main(String[] strr) {
int small, pos;
int arr[] = {3, 2, 10, 17, 13, 9, 330, 42, 21, 90, 100};
small = arr[0];
pos = 0;
System.out.println(" Before sorting");
for(int j=0;j<=arr.length-1;j++)
{
System.out.print(" "+arr[j]);
}
selectionSort(arr,small,pos);
System.out.println("\nAfter Sorting");
for(int j=0;j<=arr.length-1;j++)
{
System.out.print(" "+arr[j]);
}
}
}
output:
Before sorting 3 2 10 17 13 9 330 42 21 90 100
After Sorting 2 3 9 10 13 17 21 42 90 100 330
Time Complexity:
The time complexity of selection sort is O(n2) as there are two nested loops. One loop is for comparisons and another loop is for swapping between the elements.