# C Program to Implement Selection Sort

«
»
What is Selection Sort?

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.

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.

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
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 | C 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.

1. `/*`
2. ` * C Program to Implement Selection Sort`
3. ` */`
4. `#include <stdio.h>`
5. `void selectionSort(int arr[], int size);`
6. `void swap(int *a, int *b);`
7. `/*`
8. ` * Selection sort function`
9. ` */`
10. `void selectionSort(int arr[], int size)`
11. `{`
12. `    int i, j;`
13. `    for (i = 0 ;  i < size;i++)`
14. `    {`
15. `        for (j = i ; j < size; j++)`
16. `        {`
17. `            if (arr[i] > arr[j])`
18. `                swap(&arr[i], &arr[j]);`
19. `        }`
20. `    }`
21. `}`
22. ` `
23. `/* Function to swap two variables */`
24. `void swap(int *a, int *b)`
25. `{`
26. `    int temp;`
27. `    temp = *a;`
28. `    *a = *b;`
29. `    *b = temp;`
30. `}`
31. ` `
32. `/*`
33. ` * Main Function`
34. ` */`
35. `int main()`
36. `{`
37. `    int array, i, size;`
38. `    printf("How many numbers you want to sort:  ");`
39. `    scanf("%d", &size);`
40. `    printf("\nEnter %d numbers\t", size);`
41. `    printf("\n");`
42. `    for (i = 0; i < size; i++)`
43. `        scanf("%d", &array[i]);`
44. `    selectionSort(array, size);`
45. `    printf("\nSorted array is ");`
46. `    for (i = 0; i < size;i++)`
47. `        printf(" %d ", array[i]);`
48. `    return 0;`
49. `}`
Program Explanation

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(N2).
The time complexity of the above program for sorting an array is O(N2).

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).

Runtime Test Cases

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```

Method 2: Selection Sort Program in C using Iterative Approach

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.```
Program/Source Code

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.

1. `/*`
2. ` * C Program to Implement Selection Sort`
3. ` */`
4. ` `
5. `#include<stdio.h>`
6. `#include<stdlib.h> //header file for calloc function`
7. `int main() `
8. `{`
9. `    int *arr;  //Pointer variable for the array.`
10. `    int size;  //Size of the array block.`
11. `    printf("ENTER THE SIZE OF THE ARRAY: ");`
12. `    scanf("%d",&size);`
13. `    int temp=0;`
14. `    arr=(int*)calloc(size,sizeof(int));`
15. ` `
16. `    //Allocates as many as size number of blocks and returns the base address.`
17. `    //If space is insufficient, allocation fails and returns a NULL pointer.`
18. `    if(arr==NULL)`
19. `    {`
20. `        printf("SPACE COULD NOT BE ALLOCATED\n");`
21. `        return 1;//abnormal termination is specified`
22. `    }`
23. `    while(temp<size)`
24. `    {`
25. `        printf("arr[%d]= \t ",temp);`
26. `        scanf("%d",&arr[temp]);`
27. `        printf("\n");`
28. `        temp++;`
29. `    }`
30. `    printf("\n");`
31. ` `
32. `    //Printing the array before storing of the array.`
33. `    printf("BEFORE SORTING\n");`
34. `    temp=0;`
35. `    while(temp<size)`
36. `    {`
37. `        printf("arr[%d]=%d\n",temp,arr[temp]);`
38. `        temp++;`
39. `    }`
40. `    printf("\n");`
41. `    for(int i=0;i<size-1;i++)`
42. `    {`
43. `        int min=i;  //Temporarily assigning minimum number's value index with i`
44. ` `
45. `        //Loop to find smallest number from i+1-->end of the array.`
46. `        for(int j=i+1;j<size;j++)`
47. `        {`
48. `            if(arr[min]>arr[j])`
49. `            {`
50. `                min=j;`
51. `            }`
52. `        }`
53. ` `
54. `        //if i th element is smallest element, then no swapping will be done.`
55. `        if(min!=i)`
56. `        {`
57. `            //Swapping arr[min] with arr[i].`
58. `            int smallest=arr[min];`
59. `            arr[min]=arr[i];`
60. `            arr[i]=smallest;`
61. `        }`
62. `    }`
63. `    printf("AFTER SORTING\n");`
64. `    temp=0;`
65. `    while(temp<size)`
66. `    {`
67. `        printf("arr[%d]=%d\n",temp,arr[temp]);`
68. `        temp++;`
69. `    }`
70. `    free(arr);  //frees the memory chunk created for storing the array. `
71. `    return 0;`
72. `}`
Program Explanation

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 Ith 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(N2)
The above program to sort the array using selection sort has a time complexity of O(N2), 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).

Program Output:

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= 7
arr= 5
arr= -2
arr= -3

Before Sorting
arr= 7
arr= 5
arr= -2
arr= -3

After Sorting:
arr= -3
arr= -2
arr= 5
arr= 7```

Method 3: Selection Sort Program in C using Recursive Approach

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, -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={-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, hence new array will be arr={-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, 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.
Program/Source Code

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.

1. `/*`
2. ` * C Program to Implement Selection Sort using Recursion`
3. ` */`
4. ` `
5. `#include <stdio.h>`
6. `#include<stdlib.h> //header file for calloc function we used`
7. `void SelectionSort(int*,int,int); //function declaration`
8. `int main() `
9. `{`
10. `    int *arr;  //Pointer variable for the array.`
11. `    int size;  //Size of the array block.`
12. `    printf("Enter the Size of an Array: ");`
13. `    scanf("%d",&size);`
14. `    int temp=0;`
15. `    arr=(int*)calloc(size,sizeof(int));`
16. ` `
17. `    //Allocates as many as size number of blocks and returns the base address.`
18. `    if(arr==NULL)`
19. `    {`
20. `        //If space is insufficient, allocation fails and returns a NULL pointer.`
21. `        printf("SPACE COULD NOT BE ALLOCATED\n");`
22. `        return 1;  //abnormal termination is specified`
23. `    }`
24. `    while(temp<size)`
25. `    {`
26. `        printf("arr[%d] =\t",temp);`
27. `        scanf(" %d",&arr[temp]);`
28. `        printf("\n");`
29. `        temp++;`
30. `    }`
31. `    printf("\n");`
32. `    temp=0;`
33. ` `
34. `    //Printing the array before storing of the array.`
35. `    printf("Before Sorting\n");`
36. `    while(temp<size)`
37. `    {`
38. `        printf("arr[%d]=%d\n",temp,arr[temp]);`
39. `        temp++;`
40. `    }`
41. `    printf("\n");`
42. ` `
43. `    // calling the selection sort function start=0, end=size-1`
44. `    SelectionSort(arr,0,size-1);`
45. `    printf("After Sorting\n");`
46. `    temp=0;`
47. `    while(temp<size)`
48. `    {`
49. `        printf("arr[%d]=%d\n",temp,arr[temp]);`
50. `        temp++;`
51. `    }`
52. `    free(arr);  //free the pointer referenced to blocks of memory in array.`
53. `    return 0;`
54. `}`
55. ` `
56. `//recursive function for selection sort`
57. `void SelectionSort(int *arr,int start,int end)`
58. `{`
59. `    int j;`
60. `    int temp;`
61. `    int min;  // minimum element of the unordered list is stored in this variable`
62. ` `
63. `    //Base case is when start is increased up to end `
64. `    if (start==end)`
65. `    {`
66. `        return ;`
67. `    }`
68. `    else`
69. `    {`
70. `        min=start;`
71. ` `
72. `        //Loop to find minimum element in the unordered set of group.`
73. `        for(j=start+1;j<=end;j++)`
74. `        {`
75. `            if(arr[j]<arr[min])`
76. `            {`
77. `                min=j;`
78. `            }`
79. `        }`
80. ` `
81. `        if(start!=min)`
82. `        {`
83. `            temp=arr[min];`
84. `            arr[min]=arr[start];`
85. `            arr[start]=temp;`
86. `        }`
87. `        //list is ordered by one index and further sorting is done through successive calls.`
88. `        SelectionSort(arr,start+1,end);`
89. `    }`
90. `}`
Program Explanation

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(N2)
The above program to sort the array using selection sort has a time complexity of O(N2), 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].

Program Output:

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 = 4
arr = -5
arr = 3
arr = -9

Before Sorting
arr = 4
arr = -5
arr = 3
arr = -9

After Sorting:
arr = -9
arr = -5
arr = 3
arr = 4```

Method 4: Selection Sort Program in C using Functions

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

Program/Source Code

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.

1. `/*`
2. ` * C program for SELECTION sort which uses following functions`
3. ` * a) To find maximum of elements`
4. ` * b) To swap two elements`
5. ` */`
6. `#include <stdio.h>`
7. ` `
8. `int findmax(int b, int k);`
9. `void exchang(int b, int k);`
10. `void main()`
11. `{`
12. `    int array;`
13. `    int i, j, n, temp;`
14. ` `
15. `    printf("Enter the value of n \n");`
16. `    scanf("%d", &n);`
17. `    printf("Enter the elements one by one \n");`
18. `    for (i = 0; i < n; i++)`
19. `    {`
20. `        scanf("%d", &array[i]);`
21. `    }`
22. `    printf("Input array elements \n");`
23. `    for (i = 0; i < n ; i++)`
24. `    {`
25. `        printf("%d\n", array[i]);`
26. `    }`
27. ` `
28. `    /*  Selection sorting begins */`
29. `    exchang(array, n);`
30. `    printf("Sorted array is...\n");`
31. `    for (i = 0; i < n; i++)`
32. `    {`
33. `        printf("%d\n", array[i]);`
34. `    }`
35. `}`
36. ` `
37. `/*  function to find the maximum value */`
38. `int findmax(int b, int k)`
39. `{`
40. `    int max = 0, j;`
41. `    for (j = 1; j <= k; j++)`
42. `    {`
43. `        if (b[j] > b[max])`
44. `        {`
45. `            max = j;`
46. `        }`
47. `    }`
48. `    return(max);`
49. `}`
50. `void exchang(int b, int k)`
51. `{`
52. `    int  temp, big, j;`
53. `    for (j = k - 1; j >= 1; j--)`
54. `    {`
55. `        big = findmax(b, j);`
56. `        temp = b[big];`
57. `        b[big] = b[j];`
58. `        b[j] = temp;`
59. `    }`
60. `    return;`
61. `}`
Program Explanation

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(N2)
The above program to sort the array using selection sort has a time complexity of O(N2), 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).

Run Time Testcases

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```

Method 5: Selection Sort Program using Functions (Outside Main Function)

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.
Program/Source Code

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.

1. `/*`
2. ` * C program to implement selection sort using function`
3. ` */`
4. ` `
5. `#include <stdio.h>`
6. `#include<stdlib.h>  //header file for calloc function`
7. `void SelectionSort(int*,int,int);  //function declaration for selection sorting `
8. `int main() `
9. `{`
10. `    int *arr;//Pointer variable for the array.`
11. `    int size;//Size of the array block.`
12. `    int start;`
13. `    printf("ENTER THE SIZE OF THE ARRAY: ");`
14. `    scanf("%d",&size);`
15. `    int temp=0;`
16. `    arr=(int*)calloc(size,sizeof(int));`
17. ` `
18. `    //Allocates as many as size number of blocks and returns the base adress .`
19. `    if(arr==NULL)`
20. `    {`
21. `        //If space is insufficient, allocation fails and returns a NULL pointer.`
22. `        printf("SPACE COULD NOT BE ALLOCATED\n");`
23. `        return 1;//abnormal termination is specified`
24. `    }`
25. `    while(temp<size)`
26. `    {`
27. `        scanf("arr[%d] = %d",temp,&arr[temp]);`
28. `        printf("\n");`
29. `        temp++;`
30. `    }`
31. `    printf("\n");`
32. `    temp=0;`
33. ` `
34. `    //Printing the array before storing of the array.`
35. `    printf("Before Sorting\n");`
36. `    while(temp<size)`
37. `    {`
38. `        printf("%d\t",arr[temp]);`
39. `        temp++;`
40. `    }`
41. `    printf("\n");`
42. `    printf("select index from where the sorting needs to be Started \n");`
43. `    scanf("%d",&start);`
44. `    SelectionSort(arr,size,start);`
45. `    printf("After Sorting\n");`
46. `    temp=0;`
47. `    while(temp<size)`
48. `    {`
49. `        printf("arr[%d]=%d\n",temp,arr[temp]);`
50. `        temp++;`
51. `    }`
52. `    free(arr);// The C library function void free(void *ptr) deallocates the memory`
53. `    return 0;`
54. `}`
55. `void SelectionSort(int *arr,int size,int start)`
56. `{`
57. `    for(int i=start;i<size-1;i++)`
58. `    {`
59. `        int min=i;  //Temporarily assigning minimum number's value index with i`
60. ` `
61. `        //Loop to find smallest number from i+1-->end of the array.`
62. `        for(int j=i+1;j<size;j++)`
63. `        {`
64. `            if(arr[min]>arr[j])`
65. `            {`
66. `                min=j;`
67. `            }`
68. `        }`
69. ` `
70. `        //if i th element is smallest element, then no swapping will be done.`
71. `        if(min!=i)`
72. `        {`
73. `            //Swap arr[min] with arr[i].`
74. `            int smallest=arr[min];`
75. `            arr[min]=arr[i];`
76. `            arr[i]=smallest;`
77. `        }`
78. `    }`
79. `}`
Program Explanation

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 Ith 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(N2)
The above program to sort the array using selection sort has a time complexity of O(N2), 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).

Run Time Testcases

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= 34
arr= 56
arr= 89
arr= 21
arr= 54
arr= -7
select index from where the sorting needs to be Started
3

Before Sorting
arr= 34
arr= 56
arr= 89
arr= -7
arr= 21
arr= 54

After Sorting
arr= 34
arr= 56
arr= 89
arr= -7
arr= 21
arr= 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= 34
arr= 56
arr= 89
arr= 21
arr= 54
arr= -7
select index from where the sorting needs to be Started
0

Before Sorting
arr= -7
arr= 21
arr= 34
arr= 54
arr= 56
arr= 89

After Sorting
arr= -7
arr= 21
arr= 34
arr= 54
arr= 56
arr= 89```

Interesting Facts about Selection Sort Algorithm:

• Selection takes O(N2) (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”. 