Code Pumpkin

Selection Sort | Algorithms

October 8, 2017
Posted by Dipen Adroja

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.

    That's all for this topic. If you guys have any suggestions or queries, feel free to 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 🙂

    If you like the content on CodePumpkin and if you wish to do something for the community and the planet Earth, you can donate to our campaign for planting more trees at CodePumpkin Cauvery Calling Campaign.

    We may not get time to plant a tree, but we can definitely donate ₹42 per Tree.



    About the Author


    Coder, Blogger, Wanderer, Philosopher, Curious pumpkin



    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 : 124
    follow us in feedly

    Like Us On Facebook