Data Structures and Algorithms
    About Lesson

    Selection sort is a simple sorting algorithm. In selection sort, the lowest value among the unsorted elements of the array is selected in every pass and inserted into its appropriate position in the array.

    It is an in-place comparison sorting algorithm. In this algorithm, the array is divided into two parts. The first is the sorted part, and the second is the unsorted part.

    Initially, the sorted part of the array is empty, and the unsorted part is the given array. The sorted part is on the left, while the unsorted part is on the right.

    In selection sort, the lowest element is selected from the unsorted array and placed at the top of the list. Next, the second lowest element is selected and placed in the second position.

    The process continues until the array has been sorted completely.

     

    Time Complexity

    CaseTime Complexity
    Best CaseO(n2)
    Average CaseO(n2)
    Worst CaseO(n2)

     

    Best Case O(n2): It occurs when there is no sorting needed, i.e. the array is already sorted.

    Average Case O(n): The array elements are in a jumbled order that is not properly ascending and descending.

    Worst Case O(n): This occurs when the array elements need to be sorted in reverse order. In other words, suppose you have to sort an array in ascending order, but its elements are arranged in descending order.

     

    Space Complexity

    Space ComplexityO(1)
    StableYes

     

    A selection sort required extra variables for swapping. Hence, the space complexity of selection sorting is O(1).

     

    Example

    C Program

    #include <stdio.h>  
      
    void selection_sort(int a[], int n) {  
        int small;  
        
        // One by one move boundary of unsorted subarray  
        for (int i = 0; i < n-1; i++)  {  
            //minimum element in unsorted array  
            small = i; 
              
            for (int j = i+1; j < n; j++)  
                if (a[j] < a[small])  
                    small = j;  
                    
            // Swap the minimum element with the first element  
            int temp    = a[small];  
            a[small]    = a[i];  
            a[i]        = temp;  
        }  
    }  
    
    /* function to print the array */  
    void print(int a[], int n) {  
        for (int i = 0; i < n; i++)  
            printf("%d ", a[i]);  
    }  
      
    int main() {  
        int a[] = { 50, 20, 32, 13, 30, 18};
        int n = sizeof(a) / sizeof(a[0]);  
        printf("Before sorting array elements are - n");  
        print(a, n);  
        selection_sort(a, n);  
        printf("nAfter sorting array elements are - n");    
        print(a, n);  
        return 0;  
    } 

     

    Java Program

    public class SelectionSort {  
        /* function to sort an array with selection sort */  
        static void selectionSort(int a[]) {  
            int small;  
            int n = a.length;  
            for (int i = 0; i < n-1; i++) {  
                // minimum element in unsorted array 
                small = i;  
                  
                for (int j = i+1; j < n; j++)  
                    if (a[j] < a[small])  
                        small = j;  
                        
                // Swap the minimum element with the first element  
                int temp = a[small];  
                a[small] = a[i];  
                a[i] = temp;  
            }  
          
        }  
        
        /* function to print the array */  
        static void print(int a[]) {  
            int n = a.length;  
            for (int i = 0; i < n; i++)  
            System.out.print(a[i] + " ");  
        }  
      
        public static void main(String[] args) {  
            int a[] = {35, 10, 31, 11, 26}; 
            System.out.println("nBefore sorting array elements are - ");  
            print(a);  
            
            selectionSort(a);  
            System.out.println("nAfter sorting array elements are - ");  
            print(a);  
            System.out.println();  
        }  
    }