Sorting Algorithms - #1 Selection Sort
Tags: programming, beginners, webdev, algorithms
Published: 2022-01-06 10:46:25

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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/a8kfbjm3iwle3jbs7cps.png)

**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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jh0wuzeppyzexmr06ln2.png)

_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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/vujkmp3yc7ugp4ch8g4l.png)


element `2` is less than `minimum = 4`, then we update the `minimum` as `2`
![selection sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rvtyke5xq2mflhh9ksfh.png)


element `7` is not less than the `minimum = 4`, so we will not update the `minimum`. 
![selection sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/q1uk2gta4djgw7hxmyjg.png)


element `1` is less than `minimum = 4`, then we update the `minimum` as `1`.
![selection sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/etzh1if69rjj7ce4fmtn.png)

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

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

![selection sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yj84pnouxesiib2lys2m.png)

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


![selection sort](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/jkbxc3evfeb3ohmrb4uv.png)

See the `Java` solution.

## Java

```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;
   }
}


```

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