Sorting Algorithms - Selection Sort

Selection Sort  

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

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.

How Selection Sort works?

1. Consider the following unsorted array of integers.
   
   
2. The smallest number i.e. 12 is swapped with the first element in the array.
   
3. In the remaining data, 16 is the smallest number and it does not need to moved because it is already at the second position in the array.
   
4. 26 is the next smallest number and it is swapped with the third element.
   
5. Next smallest number is 42 and it is already in the correct position.
   
6. 53 is next smallest number from the remaining data and it is swapped with fifth element.
   
7. Off the two remaining numbers, 77 is the smallest one; the numbers are swapped.
   
8. The last remaining number i.e 84 is already sorted and is in the correct position. Thus the selection sort is complete and the array is sorted.
   

Algorithm:

Step 1: Set MIN to index 0.
Step 2: Search the minimum element in the array.
Step 3: Swap the minimum element with the value at MIN index.
Step 4: Increment MIN to point to next element.
Step 5: Repeat until the array is sorted.

C Program:
Here is source code of the C Program to implement Selection sort. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

#include<stdio.h>

void main()
{
    int elems[20], num, i, j, min, temp;

    printf("Enter the number of elements to be sorted: ");
    scanf("%d", &num);

    printf("Enter the elements of array: ");
    for (i=0; i<num; i++)
    {
        scanf("%d", &elems[i]);
    }

    for (i=0; i<(num-1); i++)
    {
        min = i;
        for (j=i+1; j<num; j++)
        {
            if (elems[min] > elems[j])
            {
                min = j;
            }
        }

        temp = elems[min];
        elems[min] = elems[i];
        elems[i] = temp;
    }

    printf("\nSorted Array: ");
    for (i=0; i<num; i++)
    {
        printf("%d  ", elems[i]);
    }
}

Output:

Enter the number of elements to be sorted: 5
Enter the elements of array: 10
5
7
1
3

Sorted Array: 1  3  5  7  10

Share on Google Plus

About AlgoStream

This is a short description in the author block about the author. You edit it by entering text in the "Biographical Info" field in the user admin panel.