In this tutorial, we will see what is selection sort algorithm and how it works. Suppose you have a group of students sitting in a classroom. The teacher wants the students to sit as per their heights, so that the shortest person is at the front desk, followed by taller one on the second desk, and so on. A method or technique, which can help in a systematic way to solve this task of arranging the seating of all students, is called the sorting method.

 

How It Works

The selection sort algorithm divides the input list into two parts - a sorted sublist of items which is built up from left to right at the front (left) of the list and a sublist of the remaining unsorted items that occupy the rest of the list. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging (swapping) it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right. More on wikipedia.

What is Selection Sort Algorithm [Explained with Practical example]

Also Read: What is Insertion Sort Algorithm [Explained with Practical example]

In general, any methodology which aids in arranging the elements in some order of a given parameter, can be termed a sorting method. There are several different methods, and one of them is `selection sort`. Now to sort them in ascending order of their ages, we can “select” the first person with the smallest age to sit on the first desk. And ask the current person sitting on the first desk to exchange places with this smallest aged person. Next we again “select” from the remaining persons the smallest person to sit on the second desk and make him swap his place with the current person on the 2nd desk and so on. This technique is known as ‘selection sort’.

 

Algorithm

SELECTION SORT(arr, n)

Input:- Array of keys in data. Total number of elements “n”

Output:- Sorted array in ascending order of key values.

Process:-

Step 1: Repeat Steps 2 and 3 for i = 0 to n-1

Step 2:  SET SMALL = arr[i]

SET pos = i

Repeat for j = i+1 to n

                 if (SMALL > arr[j])

SET SMALL = arr[j]

SET pos = j

Step 3: SWAP arr[i] with arr[pos]

Step 4: Stop

 

 

Algorithm Trace

Total persons(n)= 5

Initial sequence

 

Step 1

For the first position we need a person of the smallest age. We start searching from first place till the last, and find that infants age the least. So we swap the positions of the currently placed teenage boy with the infant boy.

 

Step 2

Now we look for an appropriate person for the second position in the list. Again we start checking the age of the 2nd person till the last person. Remember the first position has already got an appropriate person. As this time the smallest age person is the young girl, she would swap places with the current person in 2nd place.

 

 

Step 3

Now for the 3rd place, checking is done from 3rd person. But all subsequent person ages are bigger than the current person's age. Hence the current person in 3rd place is allowed to sit in the same place again.

 

 

Step 4

Now the 4th person is searched and so the young male is swapped with the old man.

 

Step 5

Due to previous steps, the 5th smallest aged person would be automatically in the 5th place. And hence we can stop.

 

 

Program in C

/******************************************************************************/

#include <stdio.h> 


void selection(int arr[], int n) 
{ 
    int i, j, small; 
    for (i = 0; i < n-1; i++)    // Consider the positions to be filled one by one
    { 
       small = i; //minimum element so far
       for (j = i+1; j < n; j++) 
       if (arr[j] < arr[small]) 
       small = j;  //Which is the smallest element in the array?
       int temp = arr[small];  // Swap the elements, so appropriate elements are placed.
       arr[small] = arr[i]; 
       arr[i] = temp; 

    } 
} 


void printArray(int a[], int n) /* function to print the array */ 
{ 
    int i; 
    for (i = 0; i < n; i++) 
        printf("%d ", a[i]); 
} 


int main() 
{ 
    int a[] = { 30,15,10,50,1 }; 
    int n = sizeof(a) / sizeof(a[0]); 
    printf("Before sorting array elements are - \n"); 
    printArray(a, n); 
    selection(a, n); 
    printf("\nAfter sorting array elements are - \n");   
    printArray(a, n); 
    return 0; 
}

 

Advantages

• It almost always outperform bubble sort and gnome sort algorithms.
• It performs well on a small list.
• It is an in-place sorting algorithm.
• No additional temporary storage is required beyond what is needed to hold the original list.
• It can also be used on list structures that make add and remove efficient, such as a linked list.
• It takes minimum possible number of swaps in comparison to other sorting algorithms.

 

Disadvantages

• It has poor efficiency when dealing with huge list of items.
• It requires n-squared number of steps for sorting n elements.
• It is only suitable for a list of few elements that are in random order.

 

Conclusion

The algorithm always looks for the smallest element from remaining elements, irrespective of whether the elements are already sorted or not. Thus for all the types of elements it would do the same amount of work of processing “n” elements. Thus we get an asymptotic order of n² time.  So this method is preferable for a small amount of data which are assumed to be unsorted.