**Selection sort** is a sorting algorithm in C that works by dividing an array into two parts: the sorted part and the unsorted part. Initially, the sorted part is empty, while the unsorted part contains all the elements. The algorithm repeatedly finds the smallest element from the unsorted part and swaps it with the first element in the unsorted part. This process continues until the entire array is sorted.

Here’s an explanation of how Selection Sort works with the example {40, 10, 50, 70, 30}, presented in a step-by-step format:

1. **Initial State:**

- Sorted Part: [ ]
- Unsorted Part: [40, 10, 50, 70, 30]

2. **First Pass:**

- Find the smallest element in the unsorted part, which is 10.
- Swap 10 with the first element in the unsorted part (40).
- Result: [10, 40, 50, 70, 30]

3. **Second Pass:**

- Find the smallest element in the unsorted part, which is 30.
- Swap 30 with the first element in the unsorted part (40).
- Result: [10, 30, 50, 70, 40]

4. **Third Pass:**

- Find the smallest element in the unsorted part, which is 40.
- Swap 40 with the first element in the unsorted part (40, which is itself).
- Result: [10, 30, 40, 70, 50]

5. **Fourth Pass:**

- Find the smallest element in the unsorted part, which is 50.
- Swap 50 with the first element in the unsorted part (50, which is itself).
- Result: [10, 30, 40, 50, 70]

6. **Fifth Pass (Final Pass):**

- Find the smallest element in the unsorted part, which is 70.
- Swap 70 with the first element in the unsorted part (70, which is itself).
- Result: [10, 30, 40, 50, 70]

7. **Final State:**

The entire array is now sorted in ascending order: **[10, 30, 40, 50, 70]**.

1. **Average Case (Unsorted Array):**

- Input Array: {4, 6, 1, 2, 5, 3}
- Expected Output: {1, 2, 3, 4, 5, 6}

2. **Best Case (Sorted Array):**

- Input Array: {-3, 31, 66}
- Expected Output: {-3, 31, 66}

3. **Worst Case (Reverse Sorted Array):**

- Input Array: {9, 8, 6, 3, 1}
- Expected Output: {1, 3, 6, 8, 9}

procedure selectionSort(arr: array of elements, size: integer) for i from 0 to size - 2 minIndex = i for j from i + 1 to size - 1 if arr[j] < arr[minIndex] minIndex = j swap arr[i] and arr[minIndex]

There are several ways to implement a selection sort program in the C language. Here are some different techniques:

- Selection Sort in C using Naive Approach
- Selection Sort in C using Iterative Approach
- Selection Sort Program in C using Recursion
- Selection Sort Program in C using Functions
- Selection Sort in C using Functions (Outside Main Function)

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

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 sorted sublist, which is built up from left to right at the front (left) of the list.
- The unsorted sublist, which contains items remaining to be sorted and occupies 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 as follows:

- It finds the smallest (or largest, depending on the sorting order) element in the unsorted sublist.
- It exchanges this element with the leftmost unsorted element, placing it in sorted order.
- It then moves the boundaries of the sorted and unsorted sublists one element to the right.

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

The time complexity of the selection sort algorithm 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.

/* * Selection Sort in C */ #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 in C 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

**Time Complexity:**Selection Sort has a time complexity of O(N^2), which makes it inefficient for sorting large arrays. However, it performs reasonably well when the number of elements is small, typically when n < 20.**Swaps:**Selection Sort makes a maximum of n-1 swaps for a list of size n, which is fewer swaps compared to other sorting algorithms like Bubble Sort.

**Simplicity:**It’s easy to understand and implement, making it a good choice for beginners learning about sorting algorithms.**Minimal Memory Usage:**Selection Sort doesn’t require additional memory, making it memory-efficient, especially for small datasets.**No Complex Data Structures:**It’s a straightforward algorithm that doesn’t rely on complex data structures.**Stable Sorting:**Selection Sort preserves the relative order of equal elements.**Suitable for Partially Sorted Data:**It performs reasonably well when data is partially sorted or nearly sorted, thanks to its limited number of swaps.

**Inefficiency for Large Arrays:**Its time complexity makes it slow for sorting large lists or arrays, as the number of comparisons grows significantly.**Lack of Adaptivity:**Selection Sort doesn’t take advantage of pre-sorted or partially sorted data, leading to the same number of comparisons even when some elements are already in place.- In practical scenarios, other sorting algorithms like quicksort or mergesort are generally preferred for efficient sorting, especially when dealing with substantial datasets.

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

**Related Links:**

- Selection Sort Programs in C++
- Selection Sort Programs in Java
- Selection Sort in C#
- Selection Sort in Python

**Related Posts:**

- Practice BCA MCQs
- Check Computer Science Books
- Check C Books
- Apply for C Internship
- Practice Computer Science MCQs