Selection Sort

Selection sort is an in-place comparison algorithm. It has an O(n^2) time complexity, which makes it inefficient on large lists, and has worse performance than the similar insertion sort.

The selection sort algorithm divides the input array in two parts:

1) The subarray which is already sorted.

2) Remaining subarray which is unsorted.

In every iteration of selection sort, the least element(considering ascending order) from the unsorted subarray is picked and moved to the sorted subarray.

---

For example:

arr[] = 46 24 12 20 8

// Find the minimum element in arr[0...4] // and place it at beginning 8 24 12 20 46

// Find the minimum element in arr[1...4] // and place it at beginning of arr[2...4] 8 12 20 24 46 // Find the minimum element in arr[3...4] // and place it at beginning of arr[3...4] 8 12 20 24 46

Another example:

Selection sort animation. Red is current min. Yellow is sorted list. Blue is current item.

---

Pseudo Code:

Here n is size of list(array of items) and Procedure is Selection sort.

   for i = 1 to n - 1
   /* set current element as minimum*/
      min = i    
  
      /* check the element to be minimum */

      for j = i+1 to n 
         if list[j] < list[min] then
            min = j;
         end if
      end for

      /* swap the minimum element with the current element*/
      if indexMin != i  then
         swap list[min] and list[i]
      end if
   end for
	
end procedure

---

Implementation using C:

#include <stdio.h>
#include <stdlib.h>

//function used for swapping
void swap(int *xp,int *yp)
{
    int temp=*a;
    *a=*b;
    *b=temp;
}

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;
            }
        }
        if(min_idx != i)
        {
            swap(&arr[min_idx],&arr[i]);
        }
    }
}

void printArray(int arr[], int size)
{
    int i;
    for(i=0;i<size;i++)
        printf("%d ",arr[i]);
    printf("\n");
}

int main()
{
    int arr[]={64, 25, 12, 22, 11};
    int n= sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr,n);
    printf("Sorted Array is : \n");
    printArray(arr,n);
    return 0;
}

Output:
Sorted array: 
11 12 22 25 64

---

Miscellaneous:

Time complexity: O(n^2) as there are two nested loops.

Auxiliary Space: O(1)

Stability: The default implementation is not stable. However it can be made stable.

In-place: Yes, it does not require extra space.

The only good this about selection sort is it never makes more than O(n) swaps and can be useful when memory write is a costly operation.