In our previous articles, we have seen two of the searching algorithms like Binary Search and Fibonacci Search alogorithm. In this article, we will go through Selection Sort algorithm.

Selection sort is one of the simplest sorting algorithm available. Before going into more details we will see first see why sorting is required in programming. Sorting is important in programming for the same reason it is important in everyday life. It is easier and faster to locate items in a sorted list than unsorted. 

The selection sort algorithm sorts an array by repeatedly finding the minimum element (considering ascending order) from the unsorted part and putting it at the beginning. The array will have two parts in this process. A subarray which is sorted and other subarrays which is yet to be sorted.

Algorithm

Sudo code for the selection sort will be as below:

sort(A)

for i ← 1 to n-1

   smallest ← i
   
   for j ← i + 1 to n
		if A[ j ] ≤ A[ smallest ]
			  smallest ← j
			  
   if smallest ≠ i	
		Exchange A[ j ] ↔ A[ smallest ]

Time and Space Complexity

From the code, we can see that the time complexity for selection sort is O(n²) and space complexity is O(1) .

Java Program Implementation

Let's implement the selection sort algorithm:

public void sort(int arr[])
{
	int n=arr.length;
	int min_ind;
	for(int i=0;i<n;i++)
	{
		min_ind = i;
		for(int j=i+1;j<n;j++)
		{
			if(arr[min_ind] > arr[j])
			{
				min_ind =j;
			}
		}
		if(min_ind!=i)
		{
			int temp = arr[i];
			arr[i] = arr[min_ind];
			arr[min_ind] = temp;
		}
	}
}

Advantage over Bubble Sort

In Selection sort, a maximum of n swap operations are required, whereas in Bubble Sort, up to n swap operation happens for each element, so up to n² total swap operation are required. These swap (write) operations are memory-intensive, so selection sort becomes even more efficient than Bubble sort for large lists.

In short, Selection Sort is used normally in cases where memory writes are quite expensive than memory reads.  

However, both Selection and Bubble Sort take O(n²) time, so it is not recommanded to use them in real-life applications. 

You can also check the other articles on sorting and searching such as selection sort, binary search, fibonacci search, merge sort etc. you can also go through our other articles on different algorithms and data structures.