[Algorithm] Selection sort

Selection sort

• At the i-th iteration (0 <= i <= n -1)
  
  • Given a list L, there are two parts: L[0, i-1] and L[i, n -1]
    • L[0, i -1]:  a sublist of items to be already sorted.
    • L[i, n - 1]: a sublist of items remaining to be sorted.
  • Select the minimum from the unsorted part.
  • Exchange the minimum with the i-th element in the list.

L[0, i-1](gray), L[i, n-1](green), minimum(red)

/*
repeat (numOfElements - 1) times
  set the first unsorted element as the minimum
  for each of the unsorted elements
    if element < currentMinimum
      set element as new minimum
  swap minimum with first unsorted position
*/

void SelectionSort(Data* list, int n)
{
	int min, temp;
    for (int i = 0; i < n - 1; i++)
    {
    	min = i;
        for (int j = i + 1; j < n; j++)
        {
        	// Find an index with the minimu element.
            if (list[j] < list[min])
            	min = j;
        }
        // Exchange the minimum element and the i-th element.
        SWAP(list[i], list[min], temp);
    }
}

• Time complexity
  • Best Case: 𝑂(𝑛^2)
    • The number of comparisons: 𝑛 − 1 + 𝑛 − 2 + ... + 2 + 1
  • Worst Case: 𝑂(𝑛^2)

• Selection sort is not stable.