DEV Community

Cover image for Sorting Algorithms - #1 Selection Sort
sachin26
sachin26

Posted on

Sorting Algorithms - #1 Selection Sort

Hi,devs

Today we are going to learn about the Selection Sort algorithm, How it works, and what are the pros & cons of using this algorithm. In this article, we will also measure the Time Complexity & Space Complexity of this algorithm.

Selection Sort

The main idea of this algorithm is to find the minimum ( for ascending order ) or maximum( for descending order ) element from the unsorted array and put it at the beginning of the unsorted array.

let's visually understand this algorithm.

selection sort

step-1 find a minimum element from the unsorted array.

To find the minimum element from the array, set the first element as a minimum = 5 from the unsorted array.

selection sort

repeatedly compare minimum to unsorted elements and, if minimum < unsorted element, then update the minimum.

element 4 is less than minimum = 5, then we update the minimum as 4.
selection sort

element 2 is less than minimum = 4, then we update the minimum as 2
selection sort

element 7 is not less than the minimum = 4, so we will not update the minimum.
selection sort

element 1 is less than minimum = 4, then we update the minimum as 1.
selection sort

so, 1 is the minimum element from the unsorted array.

step-2 swap minimum with beginning element of the unsorted array.

selection sort

repeat these steps, until the array is entirely sorted.
after repeating the steps, the Array looks like this.

selection sort

See the Java solution.

Java

import java.util.Arrays;
public class Main {
    public static void main(String[] args) {

      int[] arr = new int[]{3,2,1,5,9};

      System.out.println("unsorted Array : "+Arrays.toString(arr));

      selectionSort(arr); 

      System.out.println("sorted Array in ascending order : "+Arrays.toString(arr));
    }

   private static void selectionSort(int[] arr){
     int minIndex;

     for(int i=0; i<arr.length;i++){

       minIndex = i;

       for(int j =i+1;j<arr.length;j++){

        if(arr[j] < arr[minIndex]){
          minIndex = j;
        }
       }

       swap(arr,i,minIndex);
     }
   }

   private static void swap(int[] arr,int i,int j){
     int temp = arr[i];
     arr[i] = arr[j];
     arr[j] = temp;
   }
}


Enter fullscreen mode Exit fullscreen mode

Pros & Cons

  • good for the smallest data or Array.

  • perform badly on large Array.

  • it will not take more than n swaps.

  • this algorithm requires no extra memory space except temp variables.

Time & Space Complexity

Time Complexity :-
for the first time, finding the minimum element from the unsorted array required n-1 comparisons. for the second time n-2 comparisons, then so on.
so, the overall time complexity is O(n^2)

Space Complexity :-
Selection sort does not require any extra memory for sorting.
then, Space Complexity is O(1)


Thank you for reading this article. share this article with your dev friends and save it for the future.

Top comments (0)