Selection Sort Algorithms | How to sort an Array/List using Selection sort?

Data Structure / By Rakesh Saini / March 18, 2024

Selection Sort is a efficient and simple algorithms for sorting the elements by repeatedly selecting the largest or smallest element from the unsorted portion of the list and moving it to the sorted portion of the list. Lets go in deep dive.

Steps to follow for Selection Sort Algorithms

In this type of sort, pick the smallest element from the list and push it to beginning of the list by iterating two loops.

Pick smallest element in one iteration and do only single swipe.
Run the inner loop from next element j+1 till the length.
Compare that the min element is greater than the next element, if yes then swipe after completing the iteration.

Java


public class SelectionSort {
    public static void selectionSort(int[] arr) {
        int n = arr.length;
        
        // One by one move boundary of unsorted subarray
        for (int i = 0; i < n - 1; i++) {
            // Find the minimum element in unsorted array
            int min_idx = i;
            for (int j = i + 1; j < n; j++) {
                if (arr[j] < arr[min_idx]) {
                    min_idx = j;
                }
            }
            
            // Swap the found minimum element with the first element
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }

    public static void main(String[] args) {
        int[] arr = {64, 25, 12, 22, 11};
        selectionSort(arr);
        System.out.print("Sorted array: ");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
    }
}

//output:
Sorted array: 11 12 22 25 64

Dart

Same approach follows in the dart programming, only the way of declaring of variables changes.


void main(){
    List<int> data  = [5, 3, 7, 1, 8, 45, 23];
    int n = data.length;
    for(int i=0; i<n-1; i++){
        //initiliaze a smallest element's  position
        int smallest = i;
        for(int j=i+1; j<n; j++){
            if(data[smallest] > data[j]){
                //change the new smallest elements's postion
                smallest = j;
            }
        }
        //swipe that element
        int temp = data[smallest];
        data[smallest] = data[i];
        data[i] = temp;
    }
    
    print(data);
}

//output:
[1, 3, 5, 7, 8, 23, 45]

Time Complexity and Auxiliary Space Analysis

Time Complexity: O(N²) due to two iterations. We are looping the an array two times that why the time complexity is O(N²).

Auxiliary Space : O(1)

Do you know Bubble Sort Algorithms in DSA? See more examples.

Thank you for reaching out us. You can look into more Data Structure Tutorials from here. In case of any question, query and doubt, you can comment in the comment section below.