Code Pumpkin

Selection Sort | Algorithms

October 8, 2017
Posted by Pumpkin

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 ]

What we are doing in above code:

  • First, it finds the smallest element in the array.
  • Exchange that smallest element with the element at the first position.
  • Then find the second smallest element and exchange that element with the element at the second position.
  • This process continues until the complete array is sorted.

Selection Sort


Time and Space Complexity

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

Average Case

Selection Sort Average Case

Worst Case (Reverse List)

Selection Sort Worst Case

Above GIF Images are generated through  Algorithms mobile app.


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 n2 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.  

Bubble Sort

Bubble Sort Average Case

Selection Sort

Selection Sort Average Case

Above GIF Images are generated through  Algorithms mobile app.

However, both Selection and Bubble Sort take O(n2) 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.

Tags: , ,


Comments and Queries

If you want someone to read your code, please put the code inside <pre><code> and </code></pre> tags. For example:
<pre><code class="java"> 
String foo = "bar";
</code></pre>
For more information on supported HTML tags in disqus comment, click here.
Total Posts : 90
Contribute Your Articles

Interview Experiences

Subscribe Us

Like Us On Facebook