Code Pumpkin

Selection Sort | Algorithms

October 8, 2017
Posted by Pumpkin
Subscribe

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:

    
    void sort(int arr[])
    {
    	int n = arr.length;
    
    	for (int i = 0; i < n-1; i++)
    	{
    		int min_ind = i;
    		for (int j = i+1; j < n; j++){
    			if (arr[j] >= arr[min_ind])
    				min_ind = j;
    		}
    		// Swap the found minimum element with the first element
    		if(min_ind!=i)
    		{
    			int temp = arr[min_ind];
    			arr[min_ind] = arr[i];
    			arr[i] = 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.

    That's all for this topic. If you guys have any suggestions or queries, feel free drop a comment. We would be happy to add that in our post. You can also contribute your articles by creating contributor account here

    Happy learning 🙂

    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 Post : 80
    Subscribe
    Contribute Your Articles

    Interview Experiences

    Related Books

    Like Us On Facebook

    Alexa Page Rank