Skip to content

Selection Sort

Time : O(n2) Space : O(1)

  • it never makes more than O(n) swap
  • useful when memory write is a costly operation.
  • not stable, in place
void selectionSort(int arr[], int n)  
{  
    int i, j, min_idx;  

    for (i = 0; i < n-1; i++)  
    {  
        min_idx = i;  
        for (j = i+1; j < n; j++)  
        if (arr[j] < arr[min_idx])  
            min_idx = j;  

        swap(&arr[min_idx], &arr[i]);  
    }  
} 
Input : 4A 5 3 2 4B 1
Output : 1 2 3 4B 4A 5

Swapping might impact in pushing a key(let’s say A) to a position greater than the key(let’s say B) which are equal keys. which makes them out of desired order.

Stable

Selection sort can be made Stable if instead of swapping, the minimum element is placed in its position without swapping i.e. by placing the number in its position by pushing every element one step forward.

void stableSelectionSort(int a[], int n) 
{ 
    for (int i = 0; i < n - 1; i++)  
    { 

        int min = i; 
        for (int j = i + 1; j < n; j++) 
            if (a[min] > a[j]) 
                min = j; 

        int key = a[min]; 
        while (min > i)  
        { 
            a[min] = a[min - 1]; 
            min--; 
        } 
        a[i] = key; 
    } 
}