What is Selection Sort in C?
Selection sort is a comparison-based algorithm for sorting the array. For this, the array is divided into 2 parts, sorted part and an unsorted part, initially the sorted part is empty and the unsorted part is full. Find the smallest element from the unsorted array and replace it with the starting element of the unsorted part. Continue the process till the whole array is sorted.
Problem Description
We have to input an array of numbers and sort them either by creating a separate function for selection sort or in main function itself using C Programming Language. The input array can be sorted, unsorted or reverse sorted.
Selection Sort Algorithm:
selectionSort(array, size)
repeat (size – 1) times
set the first unsorted element as the min element
for each unsorted element, if element is less than currentMin
set the element as the newmin
swap min with the first unsorted position
end selectionSort
Problem Solution
1. Starting from the beginning pick one number.
2. Compare it with others one by one.
3. Replace if the other number is lesser than this one.
4. Display the result.
For example:
If we have the array as {40,10,50,70,30}
and we apply selection sort to sort the array,
then the resultant array after each iteration will be as follows:
Original array: {40, 10, 50, 70, 30}
Array after first iteration 10 -> 40 -> 50 -> 70 -> 30
Array after second iteration 10 -> 30 -> 50 -> 70 -> 40
Array after third iteration 10 -> 30 -> 40 -> 70 -> 50
Array after fourth iteration 10 -> 30 -> 40 -> 50 -> 70
Array after fifth iteration 10 -> 30 -> 40 -> 50 -> 70
Sorted array is 10 30 40 50 70
There are several ways to implement a selection sort program in the C language. Let’s look at the all different techniques to write a selection sort program.
Method 1: Selection Sort Program in C using Naive Approach
In this approach, we will sort the elements of the array using a selection sort algorithm.
Expected Input and Output
1. Average case (Unsorted array): When the input array has random distribution of numbers.
For example:
If the input array is {4, 6, 1, 2, 5, 3}
the expected output array will have data as {1, 2, 3, 4, 5, 6}
2. Best case (Sorted Array): When the input array is already sorted, in that case we have to make minimum number of swaps.
For example:
Check this: BCA MCQs | Computer Science Books
If the input array has data as {-3, 31, 66}
then the expected output array will have data as {-3, 31, 66}
3. Worst Case (Reverse sorted array): When the array is sorted in reverse manner, in that case we have to make maximum number of swaps.
For example:
If the input array has elements as {9, 8, 6, 3, 1}
then the output array will have data as {1, 3, 6, 8, 9}
Program/Source Code
Here is source code of the C Program to sort an array of integers using Selection Sort Algorithm. The program is successfully compiled and tested using Codeblocks gnu/gcc compiler on Windows 10. The program output is also shown below.
/*
* C Program to Implement Selection Sort
*/
#include
void selectionSort(int arr[], int size);
void swap(int *a, int *b);
/*
* Selection sort function
*/
void selectionSort(int arr[], int size)
{
int i, j;
for (i = 0 ; i < size;i++)
{
for (j = i ; j < size; j++)
{
if (arr[i] > arr[j])
swap(&arr[i], &arr[j]);
}
}
}
/* Function to swap two variables */
void swap(int *a, int *b)
{
int temp;
temp = *a;
*a = *b;
*b = temp;
}
/*
* Main Function
*/
int main()
{
int array[10], i, size;
printf(“How many numbers you want to sort: “);
scanf(“%d”, &size);
printf(“\nEnter %d numbers\t”, size);
printf(“\n”);
for (i = 0; i < size; i++)
scanf("%d", &array[i]);
selectionSort(array, size);
printf("\nSorted array is ");
for (i = 0; i < size;i++)
printf(" %d ", array[i]);
return 0;
}