Selection Sorting

Selection Sorting in Data Structure

The most fundamental sorting algorithm is selection sorting. This algorithm sorts the array by finding the smallest element and exchanging it with the element in the first position, then finding the second smallest element and exchanging it with the element in the second place, and so on until the entire array is sorted.

How Selection Sorting Works

• The smallest element found in the first pass is 1, so it is placed in the first position. 
• After that, the smallest element is searched from the remaining of the elements, and the smallest is 3, so it is placed in the second position. 
• Then, among the remaining elements, we look for the smallest and place it in third position, and so on, until the 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)