Selection Sorting

Selection sorting is conceptually the most simplest sorting algorithm. This algorithm first finds the smallest element in the array and exchanges it with the element in the first position, then find the second smallest element and exchange it with the element in the second position, and continues in this way until the entire array is sorted.

Note: Selection sort is an unstable sort i.e it might change the occurrence of two similar elements in the list while sorting. But it can also be a stable sort when it is implemented using linked list data structures.

---

How Selection Sorting Works

In the first pass, the smallest element found is 1, so it is placed at the first position, then leaving the first element, next smallest element is searched from the rest of the elements. We get 3 as the smallest, so it is then placed at the second position. Then leaving 1 and 3, we search for the next smallest element from the rest of the elements and put it at third position and keep doing this until array is sorted.

---

Sorting using Selection Sort Algorithm

void selectionSort(int a[], int size)
{
  int i, j, min, temp;
  for(i=0; i < size-1; i++ )
  {
    min = i;   //setting min as i
    for(j=i+1; j < size; j++)
    {
      if(a[j] < a[min])   //if element at j is less than element at min position
      {
       min = j;    //then set min as j
      }
    }
   temp = a[i];
   a[i] = a[min];
   a[min] = temp;
  }
}

---

Complexity Analysis of Selection Sorting

Worst Case Time Complexity : O(n2)
Best Case Time Complexity : O(n2)
Average Time Complexity : O(n2)
Space Complexity : O(1)