Selection sort in C 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.

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.

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

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 afterfirstiteration 10 -> 40 -> 50 -> 70 -> 30 Array afterseconditeration 10 -> 30 -> 50 -> 70 -> 40 Array afterthirditeration 10 -> 30 -> 40 -> 70 -> 50 Array afterfourthiteration 10 -> 30 -> 40 -> 50 -> 70 Array afterfifthiteration 10 -> 30 -> 40 -> 50 -> 70Sorted 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.

- Selection Sort Program using Naive Approach
- Selection Sort Program using Iterative Approach
- Selection Sort Program using Recursive Approach
- Selection Sort Program using Functions
- Selection Sort Program using Functions (Outside Main Function)

In this approach, we will sort the elements of the array using a selection sort algorithm.

**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:

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}

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 <stdio.h>`

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;

`}`

1. The algorithm divides the input list into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items remaining to be sorted that occupy the rest of the list.

2. Initially, the sorted sublist is empty and the unsorted sublist is the entire input list.

3. The algorithm proceeds by finding the smallest (or largest, depending on sorting order) element in the unsorted sublist, exchanging it with the leftmost unsorted element (putting it in sorted order), and moving the sublist boundaries one element to the right.

**Time Complexity: O(N ^{2}).**

The time complexity of the above program for sorting an array is O(N

^{2}).

**Space Complexity: O(1).**

In this program, we are not initializing an array or other data types that take a lot of storage. Therefore, our space complexity is constant, i.e., O(1).

**Testcase 1:** In this case, we are entering all unsorted elements, so the input array is {4, 6, 1, 2, 5, 3}.

How many numbers you want to sort: 6 Enter 6 numbers 4 6 1 2 5 3 Sorted array is 1 2 3 4 5 6

**Testcase 2:** In this case, we are entering all sorted elements, so the input array is {-3, 31, 66}.

How many numbers you want to sort: 3 Enter 3 numbers -3 31 66 Sorted array is -3 31 66

**Testcase 3:** In this case, all sorted elements are entered in reverse order, so the input array is {9, 8, 6, 3, 1}.

How many numbers you want to sort: 5 Enter 5 numbers 9 8 6 3 1 Sorted array is 1 3 6 8 9

The procedure of this iterative approach is to iterate a loop from 0 to N-1. (N = size of the array) with counter variable i. This loop contains an inner loop that finds the smallest element from the index (i+1) to index (n). If the unsorted array does not have the smallest element at the beginning, it is swapped. Otherwise there is no exchange.

**Example:**

Given array = {5, 7, -2, -3}

{5, 7, -2, -3} -> Minimum of unsorted array = -3, replace with 5 {-3, 7, -2, 5} -> Minimum of unsorted array = -2, replace with 7 {-3, -2, 7, 5} -> Minimum of unsorted array = 5, replace with 7 {-3, -2, 5, 7} -> 7 is the only element that does not need to be continued, so the array is sorted. {-3, -2, 5, 7} -> Sorted Array.

Here is the source code of the C program to sort a dynamic array in ascending order 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<stdio.h>`

`#include<stdlib.h> //header file for calloc function`

int main()

`{`

int *arr; //Pointer variable for the array.

int size; //Size of the array block.

printf("ENTER THE SIZE OF THE ARRAY: ");

scanf("%d",&size);

int temp=0;

arr=(int*)calloc(size,sizeof(int));

`//Allocates as many as size number of blocks and returns the base address.`

`//If space is insufficient, allocation fails and returns a NULL pointer.`

if(arr==NULL)

`{`

printf("SPACE COULD NOT BE ALLOCATED\n");

return 1;//abnormal termination is specified

`}`

while(temp<size)

`{`

printf("arr[%d]= \t ",temp);

scanf("%d",&arr[temp]);

printf("\n");

`temp++;`

`}`

printf("\n");

`//Printing the array before storing of the array.`

printf("BEFORE SORTING\n");

temp=0;

while(temp<size)

`{`

printf("arr[%d]=%d\n",temp,arr[temp]);

`temp++;`

`}`

printf("\n");

for(int i=0;i<size-1;i++)

`{`

int min=i; //Temporarily assigning minimum number's value index with i

`//Loop to find smallest number from i+1-->end of the array.`

for(int j=i+1;j<size;j++)

`{`

if(arr[min]>arr[j])

`{`

min=j;

`}`

`}`

`//if i th element is smallest element, then no swapping will be done.`

if(min!=i)

`{`

`//Swapping arr[min] with arr[i].`

int smallest=arr[min];

arr[min]=arr[i];

arr[i]=smallest;

`}`

`}`

printf("AFTER SORTING\n");

temp=0;

while(temp<size)

`{`

printf("arr[%d]=%d\n",temp,arr[temp]);

`temp++;`

`}`

free(arr); //frees the memory chunk created for storing the array.

return 0;

`}`

1. Take a number as input and store in the **size** variable.

2. Use **calloc** function to dynamically allocate memory. If the memory is not allocated, either abort the program or take the array elements as input.

3. Print the array elements before sorting

4. Starts an outer loop and iterates over **i** from **0** to **size – 2**.

5. Initialise **min** variable stores the index of the smallest element in the unsorted part.

6. Temporarily set the **min** variable to **arr[i]**. i.e. **min=arr[i]**

7. Start the inner loop and iterate **j** from **i+1** to **n**.

8. If **arr[j] < arr[min]**, then assign **min = j**

9. If **min!=i**, means the smallest element is not at I^{th} position then swap **arr[i]** with **arr[min]**.

10. Otherwise, no swapping is performed. Outer loop ends.

11. Print the sorted array.

**Time Complexity: O(N ^{2})**

The above program to sort the array using selection sort has a time complexity of O(N

^{2}), because first the outer loop iterated from 0 to the second last of the array and the inner loop also iterates the whole array. There is also array printing and scanning, both of which take linear time.

**Space Complexity: O(1)**

In this program, we are not initializing an array or other data types that take a lot of storage. We are just initializing the auxiliary variables temporarily for swapping. Therefore, our space complexity is constant, i.e., O(1).

In this case, all sorted elements are entered in reverese order, therefore the input array is {7, 5, -2, -3}.

Enter the Size of the Array: 4 arr[0]= 7 arr[1]= 5 arr[2]= -2 arr[3]= -3 Before Sorting arr[0]= 7 arr[1]= 5 arr[2]= -2 arr[3]= -3 After Sorting: arr[0]= -3 arr[1]= -2 arr[2]= 5 arr[3]= 7

Selection sort works by finding the smallest unsorted item in the list and swapping it with the item in the current position. It is used for sorting unsorted list of elements. To find the sorted position of an element, find the minimum element and swap it with the first element of the unordered array, and sort the array where you called the function until you’ve sorted the entire array.

**Example:**

**Let arr[4] = {4, -5, 3, -9}**

**SelectionSort(arr,start,end)**is the function that sorts the array**arr**from a**start**index to**end**index.**Base case:**recursion stops when**start==end**.- In the first call, we pass
**SelectionSort(arr,0,3)**=> this function call finds the smallest element from index 0 to 3 and swaps it with 0 index. - So the updated array is
**arr[4]={-9,-5,3,4}**and also calls**SelectionSort(arr,1,3)** **SelectionSort(arr,1,3)**=> finds the minimum element from index 1 to index 3 and swap with**arr[1]**, hence new array will be**arr[4]={-9,-5,3,4}**. -5 was the smallest element, so we do not exchange it. It also calls**SelectionSort(arr,2,3)**.**SelectionSort(2,3)**=> finds the minimum element from index 2 to index 3 and swap it with**arr[2]**, but now swapping is not needed as it is already at the sorted position then it calls**SelectionSort(arr,3,3)****SelectionSort(arr,3,3)**=> Base case is reached we return the control.

Here is the source code of a C program to Sort the array in ascending order in a recursive approach. The C Program is successfully compiled and run on a Windows system. The program output is also shown below.

`/*`

`* C Program to Implement Selection Sort using Recursion`

`*/`

`#include <stdio.h>`

`#include<stdlib.h> //header file for calloc function we used`

void SelectionSort(int*,int,int); //function declaration

int main()

`{`

int *arr; //Pointer variable for the array.

int size; //Size of the array block.

printf("Enter the Size of an Array: ");

scanf("%d",&size);

int temp=0;

arr=(int*)calloc(size,sizeof(int));

`//Allocates as many as size number of blocks and returns the base address.`

if(arr==NULL)

`{`

`//If space is insufficient, allocation fails and returns a NULL pointer.`

printf("SPACE COULD NOT BE ALLOCATED\n");

return 1; //abnormal termination is specified

`}`

while(temp<size)

`{`

printf("arr[%d] =\t",temp);

scanf(" %d",&arr[temp]);

printf("\n");

`temp++;`

`}`

printf("\n");

temp=0;

`//Printing the array before storing of the array.`

printf("Before Sorting\n");

while(temp<size)

`{`

printf("arr[%d]=%d\n",temp,arr[temp]);

`temp++;`

`}`

printf("\n");

`// calling the selection sort function start=0, end=size-1`

SelectionSort(arr,0,size-1);

printf("After Sorting\n");

temp=0;

while(temp<size)

`{`

printf("arr[%d]=%d\n",temp,arr[temp]);

`temp++;`

`}`

free(arr); //free the pointer referenced to blocks of memory in array.

return 0;

`}`

`//recursive function for selection sort`

void SelectionSort(int *arr,int start,int end)

`{`

int j;

int temp;

int min; // minimum element of the unordered list is stored in this variable

`//Base case is when start is increased up to end`

if (start==end)

`{`

return ;

`}`

`else`

`{`

min=start;

`//Loop to find minimum element in the unordered set of group.`

for(j=start+1;j<=end;j++)

`{`

if(arr[j]<arr[min])

`{`

min=j;

`}`

`}`

if(start!=min)

`{`

temp=arr[min];

arr[min]=arr[start];

arr[start]=temp;

`}`

`//list is ordered by one index and further sorting is done through successive calls.`

SelectionSort(arr,start+1,end);

`}`

`}`

1. Take a number as input and store in the **size** variable.

2. **calloc** function allocates the size number of blocks and returns the pointer to the first element / block to **arr**.

3. If **arr==NULL**, then the program is terminated or else input the array.

4. Call the function to sort the array. i.e. **selection sort(arr,0,size-1)**

5. If **start!= end**, then we have a base situation in which our array is sorted. As we came to the end of the array.

6. Else: we assume that the start has the minimum element so we assign **min** to start, Now iterate through the array to find if there is any element smaller than **arr[min]**, if yes then we assign **min** to that index.

7. If **min** is not equal to start, then we just swap the two elements. Otherwise, no swapping is done as elements are placed at their sorted position.

8. Reclusively call the function **SelectionSort(arr,start+1,end)**. Start is increased by 1 because we have sorted the array by one index.

**Time Complexity: O(N ^{2})**

The above program to sort the array using selection sort has a time complexity of O(N

^{2}), because first the outer loop iterated from 0 to the second last of the array and the inner loop also iterates the whole array. There is also array printing and scanning, both of which take linear time.

**Space Complexity: O(n+k)**

In this program, we are using a call stack as it is a recursive based approach that takes up as much storage space as the number of elements in the array. Hence, our space complexity is linear, i.e., O(n+k) [*k=constant].

In this case, the array size is 4 and the input array is {4, -5, 3, 9}.

Enter the Size of the Array: 4 arr[0] = 4 arr[1] = -5 arr[2] = 3 arr[3] = -9 Before Sorting arr[0] = 4 arr[1] = -5 arr[2] = 3 arr[3] = -9 After Sorting: arr[0] = -9 arr[1] = -5 arr[2] = 3 arr[3] = 4

In this approach, we implements selection sort method using functions. Selection sort is among the simplest of sorting techniques.

Here is source code of the C program to implement selection sort method using functions. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

`/*`

`* C program for SELECTION sort which uses following functions`

`* a) To find maximum of elements`

`* b) To swap two elements`

`*/`

`#include <stdio.h>`

int findmax(int b[10], int k);

void exchang(int b[10], int k);

void main()

`{`

int array[10];

int i, j, n, temp;

printf("Enter the value of n \n");

scanf("%d", &n);

printf("Enter the elements one by one \n");

for (i = 0; i < n; i++)

`{`

scanf("%d", &array[i]);

`}`

printf("Input array elements \n");

for (i = 0; i < n ; i++)

`{`

printf("%d\n", array[i]);

`}`

`/* Selection sorting begins */`

exchang(array, n);

printf("Sorted array is...\n");

for (i = 0; i < n; i++)

`{`

printf("%d\n", array[i]);

`}`

`}`

`/* function to find the maximum value */`

int findmax(int b[10], int k)

`{`

int max = 0, j;

for (j = 1; j <= k; j++)

`{`

if (b[j] > b[max])

`{`

max = j;

`}`

`}`

return(max);

`}`

void exchang(int b[10], int k)

`{`

int temp, big, j;

for (j = k - 1; j >= 1; j--)

`{`

big = findmax(b, j);

temp = b[big];

b[big] = b[j];

b[j] = temp;

`}`

return;

`}`

1. Take a number as input and store in the **n** variable.

2. It performs selection sort according to functions such as finding the maximum value of an element or exchanging two elements.

3. Print the sorted array.

**Time Complexity: O(N ^{2})**

The above program to sort the array using selection sort has a time complexity of O(N

^{2}), because first the outer loop iterated from 0 to the second last of the array and the inner loop also iterates the whole array. There is also array printing and scanning, both of which take linear time.

**Space Complexity: O(1)**

In this program, we are not initializing an array or other data types that take a lot of storage. We are just initializing the auxiliary variables temporarily for swapping. Therefore, our space complexity is constant, i.e., O(1).

In this case, the array size is 4 and the input array is {57, 90, 34, 78}.

Enter the value of n 4 Enter the elements one by one 57 90 34 78 Input array elements 57 90 34 78 Sorted array is... 34 57 78 90

This is very similar to the iterative approach but instead of writing the code in the main function, we write a new function to sort an array. We can also specify the starting index of sorting; in this way, we can reuse our function whenever necessary.

**Example:**

- Given
**arr[]={34, 56, 89, 21, 54, -7}**. Sort the array from index 3 to index 5 (last index). - Call the function
**SelectionSort(arr,3,6)**, 3=starting index; 6=size of the array. **Arr[]={34, 56, 89, 21, 54, -7}**(minimum element from index 3 to last index = -7)- So, swap that -7 with 21 i.e.
**Arr[]={34, 56, 89, -7, 54, 21}** - Now, minimum element from index 4 to last index the element is 21. So, swap 21 with 54.

i.e.**Arr[]= {34, 56, 89, -7, 21, 54}** - Since the outer loop iterates from starting index to second last index of the array, we can assume that the operation is complete and we get the sorted subarray.

Here is the source code of a C program to Sort the array in ascending order in a function-based approach. The C Program is successfully compiled and run on a Windows system. The program output is also shown below.

`/*`

`* C program to implement selection sort using function`

`*/`

`#include <stdio.h>`

`#include<stdlib.h> //header file for calloc function`

void SelectionSort(int*,int,int); //function declaration for selection sorting

int main()

`{`

int *arr;//Pointer variable for the array.

int size;//Size of the array block.

int start;

printf("ENTER THE SIZE OF THE ARRAY: ");

scanf("%d",&size);

int temp=0;

arr=(int*)calloc(size,sizeof(int));

`//Allocates as many as size number of blocks and returns the base adress .`

if(arr==NULL)

`{`

`//If space is insufficient, allocation fails and returns a NULL pointer.`

printf("SPACE COULD NOT BE ALLOCATED\n");

return 1;//abnormal termination is specified

`}`

while(temp<size)

`{`

scanf("arr[%d] = %d",temp,&arr[temp]);

printf("\n");

`temp++;`

`}`

printf("\n");

temp=0;

`//Printing the array before storing of the array.`

printf("Before Sorting\n");

while(temp<size)

`{`

printf("%d\t",arr[temp]);

`temp++;`

`}`

printf("\n");

printf("select index from where the sorting needs to be Started \n");

scanf("%d",&start);

SelectionSort(arr,size,start);

printf("After Sorting\n");

temp=0;

while(temp<size)

`{`

printf("arr[%d]=%d\n",temp,arr[temp]);

`temp++;`

`}`

free(arr);// The C library function void free(void *ptr) deallocates the memory

return 0;

`}`

void SelectionSort(int *arr,int size,int start)

`{`

for(int i=start;i<size-1;i++)

`{`

int min=i; //Temporarily assigning minimum number's value index with i

`//Loop to find smallest number from i+1-->end of the array.`

for(int j=i+1;j<size;j++)

`{`

if(arr[min]>arr[j])

`{`

min=j;

`}`

`}`

`//if i th element is smallest element, then no swapping will be done.`

if(min!=i)

`{`

`//Swap arr[min] with arr[i].`

int smallest=arr[min];

arr[min]=arr[i];

arr[i]=smallest;

`}`

`}`

`}`

This is the same as the iterative approach just we have shifted the loops outside of the main function scope.

1. Take a number as input and store in the **size** variable.

2. Use **calloc** function to dynamically allocate memory. If the memory is not allocated, either abort the program or take the array elements as input.

3. Take a user input to determine which index to sort elements from (0-based indexing is utilised); if you wish to sort the entire array, simply enter 0.

4. Call the **SelectionSort** function with passing them **arr**, the address holding pointer variable, start the index from sorting needs to be started and size, the size of the array.

5. If start = 0, sorting starts at index 0. If start = 2, sorting starts at index 2.

6. Starts an outer loop and iterates over **i** from **0** to **size – 2**.

7. Initialise **min** variable stores the index of the smallest element in the unsorted part.

8. Temporarily set the **min** variable to **arr[i]**. i.e. **min=arr[i]**

9. Start the inner loop and iterate **j** from **i+1** to **n**.

10. If **arr[j] < arr[min]**, then assign **min = j**

11. If **min!=i**, means the smallest element is not at I^{th} position then swap **arr[i]** with **arr[min]**.

12. Otherwise, no swapping is performed. Outer loop ends.

13. Print the sorted array.

**Time Complexity: O(N ^{2})**

The above program to sort the array using selection sort has a time complexity of O(N

^{2}), because first the outer loop iterated from 0 to the second last of the array and the inner loop also iterates the whole array. There is also array printing and scanning, both of which take linear time.

**Space Complexity: O(1)**

In this program, we are not initializing an array or other data types that take a lot of storage. We are just initializing the auxiliary variables temporarily for swapping. Therefore, our space complexity is constant, i.e., O(1).

**Testcase 1:** In this case, the array size is 6 and the input array is {34, 56, 89, 21, 54, -7} and the index at which sorting should begin is “3”.

Enter the Size of the Array: 6 arr[0]= 34 arr[1]= 56 arr[2]= 89 arr[3]= 21 arr[4]= 54 arr[5]= -7 select index from where the sorting needs to be Started 3 Before Sorting arr[0]= 34 arr[1]= 56 arr[2]= 89 arr[3]= -7 arr[4]= 21 arr[5]= 54 After Sorting arr[0]= 34 arr[1]= 56 arr[2]= 89 arr[3]= -7 arr[4]= 21 arr[5]= 54

**Testcase 2:** To sort the entire array, simply supply 0 to the start variable. The array size is 6, and the input array has the values {34, 56, 89, 21, 54, -7}.

Enter the Size of the Array: 6 arr[0]= 34 arr[1]= 56 arr[2]= 89 arr[3]= 21 arr[4]= 54 arr[5]= -7 select index from where the sorting needs to be Started 0 Before Sorting arr[0]= -7 arr[1]= 21 arr[2]= 34 arr[3]= 54 arr[4]= 56 arr[5]= 89 After Sorting arr[0]= -7 arr[1]= 21 arr[2]= 34 arr[3]= 54 arr[4]= 56 arr[5]= 89

**Interesting Facts about Selection Sort Algorithm:**

- Selection takes O(N
^{2}) (quadratic curve) time, n=number of items in for sorting the array. This makes selection sort algorithm inefficient in places where number of element is higher. However, it is pretty efficient in sorting list where n<20 . - This algorithm is fruitful where swapping operation is costly as it makes a maximum of n-1 swaps for a list of size n. compared to bubble sort where number of swaps are much higher.

To practice programs on every topic in C, please visit “Programming Examples in C”, “Data Structures in C” and “Algorithms in C”.

**Next Steps:**

- Get Free Certificate of Merit in C Programming
- Participate in C Programming Certification Contest
- Become a Top Ranker in C Programming
- Take C Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

**Related Posts:**

- Watch Advanced C Programming Videos
- Practice Computer Science MCQs
- Buy C Books
- Buy Computer Science Books
- Apply for Computer Science Internship