Selection Sort

Unknown 00:05
Selection Sort is conceptually the most simplest sorting algorithm which sorts an array by repeatedly finding the minimum element (considering ascending order) from unsorted part and putting it at the beginning.
The algorithm divides the input list into two parts:
  • The sublist of items already sorted
  • The sublist of items remaining to be sorted that occupy the rest of the list.
In each iteration, the minimum element (considering ascending order) from the unsorted sub-list is picked and moved to the sorted sub-list.

EXAMPLE
Here is an example of this sort algorithm sorting five elements:

64 25 12 22 11 // this is the initial, starting state of the array

11 25 12 22 64 // sorted sublist = {11}

11 12 25 22 64 // sorted sublist = {11, 12}

11 12 22 25 64 // sorted sublist = {11, 12, 22}

11 12 22 25 64 // sorted sublist = {11, 12, 22, 25}


11 12 22 25 64 // sorted sublist = {11, 12, 22, 25, 64}

[Reference: wikipedia]

SELECTION SORT C-CODE

// C program to implement Selection sort
#include <stdio.h>
 int main()
{
    int arr[] = {6, 3, 5, 2, 8, 10, 9};
    int n = sizeof(arr)/sizeof(arr[0]);
    //Selection Sort starts
    int i, j, min, temp;
    for (i = 1; i < n-1; i++)      
    {
         min=i;
         for (j = i+1; j <n; j++)
         {
              if(arr[j] < arr[min])
              {
                   min=j;
               }
          }
          //Swapping arr[i] and arr[min]
          temp = arr[i];
          arr[i] = arr[min];
          arr[min] = temp;
    }
    //Selection Sort ends
    printf("Sorted array: \n");
    for (int i=0; i < n; i++)
    {
        printf("%d ", arr[i]);
    }
    return 0;
}
OutputSorted array:
2  3  5  6  8  9  10

COMPLEXITY ANALYSIS

  • Best, Worst and Average Case Time Complexity: O(n*n).
  • Auxiliary Space Complexity: O(1).
Tags: