Your Web News in One Place

Help Webnuz

Referal links:

Sign up for GreenGeeks web hosting
January 6, 2022 10:46 am GMT

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 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, then we update the minimum as 4.
selection sort

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

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

element 1 is less than minimum, 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, 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;   }}

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(n2)

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.


Original Link: https://dev.to/sachin26/sorting-algorithms-1-selection-sort-1imm

Share this article:    Share on Facebook
View Full Article

Dev To

An online community for sharing and discovering great ideas, having debates, and making friends

More About this Source Visit Dev To