Selection Sort Program in C

What is Selection Sort in C?

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.

How Selection Sort works? (Step-by-Step)

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:

advertisement
advertisement
  • 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].

Expected Input and Output:

1. Average Case (Unsorted Array):

Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
  • 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}
Selection Sort Algorithm (Pseudocode):
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]
Selection Sort Programs in C:

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

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

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 <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;
}
Program Explanation

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:

advertisement
  • 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(N2).
The time complexity of the selection sort algorithm 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.

/*
 *  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;
}
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 in C 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[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

Method 3: Selection Sort 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] = {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.
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[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

Method 4: Selection Sort 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[10], int k);
  9. void exchang(int b[10], int k);
  10. void main()
  11. {
  12.     int array[10];
  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[10], 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[10], 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[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
Selection Sort Algorithm Facts:
  • 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.
Advantages of Selection Sort in C:
  • 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.
Disadvantages of Selection Sort in C:
  • 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:

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.