C Program For Selection Sort: Explanation & Step-by-Step Guide

Selection Sort is one of the simplest sorting algorithms used to arrange elements in ascending or descending order. It is a comparison-based algorithm that repeatedly selects the smallest (or largest) element from the unsorted portion of the list and moves it to the sorted portion. While it is not the most efficient for large datasets, its simplicity makes it a popular choice for learning the basics of sorting algorithms.

Selection Sort operates by systematically dividing the array into two sections: a sorted part and an unsorted part. At the start, the sorted part is empty, and the unsorted part contains all the elements of the array. With each iteration, one element is selected from the unsorted part, identified as the smallest (or largest, depending on sorting order), and moved to the sorted part.

Algorithm for Selection Sort in C

1. Start with the first element of the array.
2. Assume the first element is the smallest in the unsorted portion.
3. Traverse through the unsorted portion of the array (all elements after the current position).
4. Compare each element with the current smallest element:
5. If a smaller element is found, update the smallest element's index.
6. Once the smallest element in the unsorted part is identified, swap it with the first unsorted element (the current position).
7. This moves the smallest element into its correct position in the sorted part.
8. Increment the boundary of the sorted part by one (move to the next position).
9. Repeat steps 1 to 3 for the remaining unsorted part of the array.
10. Continue until the entire array is sorted.

Example: Sorting an Array [29, 10, 14, 37, 13] in Ascending Order

Here is a step-by-step explanation of sorting the array [29, 10, 14, 37, 13] in ascending order using Selection Sort in c:

Initial Array: [29, 10, 14, 37, 13]

We will sort the array by finding the smallest element in the unsorted part and swapping it with the first unsorted element.

Step 1: Find the smallest in the whole array

Unsorted portion: [29, 10, 14, 37, 13]

Compare each element:

• 29>10 → Update smallest to 10.
• 10<14, 10<37, 10<13 → 10 is still the smallest.

Swap 1010 with the first element (29):

Array after Step 1: [10, 29, 14, 37, 13]

Step 2: Find the smallest in the remaining unsorted part

Unsorted portion: [29, 14, 37, 13]

Compare each element:

• 29>14 → Update smallest to 1414.
• 14<37, 14>13 → Update smallest to 1313.

Swap 1313 with the first unsorted element (29):

Array after Step 2: [10, 13, 14, 37, 29]

Step 3: Find the smallest in the remaining unsorted part

Unsorted portion: [14, 37, 29]

Compare each element:

• 14<37, 14<29 → 14 is already the smallest.

No swap is needed.

Array after Step 3: [10, 13, 14, 37, 29]

Step 4: Find the smallest in the remaining unsorted part

Unsorted portion: [37, 29]

Compare:

• 37>29 → Update smallest to 2929.

Swap 29 with 37:

Array after Step 4: [10, 13, 14, 29, 37]

Final Sorted Array: [10, 13, 14, 29, 37]

Each step confirms the smallest element is placed in its correct position, and the process continues until the array is sorted.

Key Characteristics of Selection Sort

• Time Complexity: The time complexity is O(n²) in the best, average, and worst cases.
• Space Complexity: The space complexity is O(1) because it is an in-place sorting algorithm, requiring no additional storage for sorting.
• Stability: Selection Sort is not a stable sorting algorithm as equal elements may not retain their original relative order.
• Adaptability: This algorithm is not adaptive; it performs the same number of comparisons regardless of the initial order of the elements.

Here is a complete implementation of the Selection Sort C code. This code sorts an array of integers in ascending order by repeatedly finding the smallest element in the unsorted portion and swapping it with the first unsorted element. Here is the C Program for Selection Sort:

C Program for Selection Sort

#include <stdio.h>

// Function to perform selection sort
void selectionSort(int arr[], int n) {
    int i, j, min_idx;

    // Traverse through all array elements
    for (i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted portion
        min_idx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // Swap the found minimum element with the first element
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}

// Function to print an array
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// Main function
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    selectionSort(arr, n);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Input

int arr[] = {64, 25, 12, 22, 11};

Explanation of the Code

1. Functionality of the Code

The program shows the implementation of the Selection Sort algorithm in C. Selection Sort is a simple sorting technique that iterates through the array and divides it into two parts: the sorted part and the unsorted part. With each pass, the smallest element from the unsorted portion is identified and moved to its correct position in the sorted part by swapping it with the first unsorted element. 

2. Selection Sort Function

The selectionSort function is the core of the program. It takes two arguments: the array arr[] to be sorted and its size n. The outer loop iterates through the array from the first to the second-to-last element. For each iteration, the function assumes the current element (indexed by i) is the smallest in the unsorted portion. 

3. Printing the Array

The printArray function is a utility function used to display the contents of an array. It accepts the array and its size as arguments. Using a for loop, it iterates through each element in the array, printing them one by one, separated by spaces. 

4. Main Function

The main function initializes an integer array, arr, with a set of predefined values: {64, 25, 12, 22, 11}. It calculates the size of the array using the formula sizeof(arr) / sizeof(arr[0]), which divides the total memory size of the array by the size of a single element. 

Output

Original array: 
64 25 12 22 11 
Sorted array: 
11 12 22 25 64 

Complexity of the Code

Time Complexity

• Best Case: O(n^2)
  Even if the array is already sorted, the algorithm still performs n(n−1)/2 comparisons as it checks every pair of elements.
• Worst Case: O(n^2)
  The algorithm makes the same number of comparisons regardless of input order because it always scans the unsorted portion to find the minimum.

Space Complexity

• Space Complexity: O(1)
  The algorithm is in place and requires no extra memory apart from a few variables (e.g., min_idx, temp).

A recursive implementation of Selection Sort is a version of the algorithm that sorts an array by repeatedly calling itself on smaller portions of the array. Instead of using loops to iterate through the array, the function breaks the problem into smaller subproblems and solves them recursively. Here are C Program for Selection Sort recursively:

C Program for Selection Sort with Recursive Implementation

#include <stdio.h>

// Recursive function to perform selection sort
void recursiveSelectionSort(int arr[], int n, int index) {
    // Base case: If the entire array is sorted
    if (index == n - 1) {
        return;
    }

    // Find the minimum element in the unsorted portion
    int min_idx = index;
    for (int j = index + 1; j < n; j++) {
        if (arr[j] < arr[min_idx]) {
            min_idx = j;
        }
    }

    // Swap the smallest element with the current index
    int temp = arr[min_idx];
    arr[min_idx] = arr[index];
    arr[index] = temp;

    // Recursive call for the remaining unsorted portion
    recursiveSelectionSort(arr, n, index + 1);
}

// Main function
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    printArray(arr, n);

    recursiveSelectionSort(arr, n, 0);

    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

Input

int arr[] = {64, 25, 12, 22, 11};

Explanation of the Code

This program implements the Selection Sort algorithm recursively. Instead of using iterative loops for sorting, the program employs a recursive function, recursiveSelectionSort, to sort the array.

1. Recursive Selection Sort Function

The function recursiveSelectionSort sorts an array arr[] by processing one element at a time, starting from the current index and moving towards the end of the array.

• Base Case: The recursion stops when the current index (index) reaches the second-to-last position (n-1), as only one element remains unsorted, which is already in place.
• Finding the Minimum Element: The function identifies the smallest element in the unsorted portion of the array (from index to n-1) using a loop. The index of this smallest element is stored in min_idx.
• Swapping: The smallest element at min_idx is swapped with the element at the current index to place it in its correct position.
• Recursive Call: After placing the smallest element in the correct position, the function recursively calls itself with the next index (index + 1) to sort the remaining unsorted portion of the array.

2. Printing the Array

The printArray function is important for displaying the array contents before and after sorting. It iterates through the array and prints each element separated by spaces. This function is reused from the previous iterative version to maintain consistency.

3. Main Function

The main function initializes an unsorted array arr[] with predefined values: {64, 25, 12, 22, 11}. It calculates the size of the array and prints the original array using printArray.

Output

Original array: 
64 25 12 22 11 
Sorted array: 
11 12 22 25 64 

Complexity of the Code

Time Complexity:

1. Best Case: O(n^2)
   The algorithm performs n(n−1)/2 comparisons, regardless of the input being sorted or unsorted, due to the nested iteration and recursion.
2. Worst Case: O(n^2)
   The same number of comparisons and swaps are performed in the worst case since every element must be checked.

Space Complexity:

1. Space Complexity: O(n)
   Due to the recursive function calls, the algorithm uses stack space proportional to the size of the input array, leading to O(n) additional memory usage.

Selection Sort can be implemented using functions to improve code modularity and readability. By defining a separate function for selection sort, we can call it multiple times as needed. This approach helps in keeping the main() function clean and easy to understand.

Example Code

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i, j, minIdx, temp;
    for (i = 0; i < n - 1; i++) {
        minIdx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

void printArray(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Output

Input Array: {64, 25, 12, 22, 11}
Sorted array: 11 12 22 25 64

findmax Function in Selection Sort

In Selection Sort, the findmax function can be used to find the maximum element in a given range of an array. Instead of searching for the minimum element (as in traditional Selection Sort), we can modify the function to locate the maximum element and place it at the correct position.

Example Code

#include <stdio.h>

int findMax(int arr[], int n) {
    int maxIdx = 0;
    for (int i = 1; i < n; i++) {
        if (arr[i] > arr[maxIdx]) {
            maxIdx = i;
        }
    }
    return maxIdx;
}

int main() {
    int arr[] = {10, 3, 5, 7, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    int maxIndex = findMax(arr, n);
    printf("Maximum element is at index: %d, Value: %d\n", maxIndex, arr[maxIndex]);

    return 0;
}

Output

Input Array: {10, 3, 5, 7, 2}
Maximum element is at index: 0, Value: 10

Selection Sort Program using Functions (Outside Main Function)

This implementation moves the selection sort logic outside the main() function, making the program more structured.

Example Code

#include <stdio.h>

void selectionSort(int arr[], int n);
void swap(int *a, int *b);

int main() {
    int arr[] = {29, 10, 14, 37, 13};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

void selectionSort(int arr[], int n) {
    int i, j, minIdx;
    for (i = 0; i < n - 1; i++) {
        minIdx = i;
        for (j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        swap(&arr[minIdx], &arr[i]);
    }
}
void swap(int *a, int *b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

Output

Input Array: {29, 10, 14, 37, 13}
Sorted array: 10 13 14 29 37

A for loop is commonly used in Selection Sort to iterate through the array and find the minimum element in each pass.

Example Code

#include <stdio.h>

void selectionSort(int arr[], int n) {
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
    }
}

int main() {
    int arr[] = {8, 4, 6, 2, 9};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Output

Input Array: {8, 4, 6, 2, 9}
Sorted array: 2 4 6 8 9

A while loop can also be used to implement Selection Sort instead of a for loop.

Example Code

#include <stdio.h>

void selectionSort(int arr[], int n) {
    int i = 0;
    while (i < n - 1) {
        int minIdx = i;
        int j = i + 1;
        while (j < n) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
            j++;
        }
        int temp = arr[minIdx];
        arr[minIdx] = arr[i];
        arr[i] = temp;
        i++;
    }
}

int main() {
    int arr[] = {50, 20, 40, 10, 30};
    int n = sizeof(arr) / sizeof(arr[0]);

    selectionSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

Output

Input Array: {50, 20, 40, 10, 30}
Sorted array: 10 20 30 40 50

Selection Sort offers several benefits that make it a very good option in certain situations. Here are some of the key advantages of using this sorting algorithm:

1. Simplicity:

Selection Sort is one of the simplest sorting algorithms, making it easy to understand and implement. Its direct approach of repeatedly finding the minimum element and swapping it with the current position confirms clarity in both logic and coding. This simplicity also makes it an excellent choice for beginners learning sorting algorithms.

2. In-Place Sorting:

The algorithm does not require any additional memory or auxiliary data structures for sorting. Since it sorts the array in place by swapping elements, it has a space complexity of O(1), which is beneficial in memory-constrained systems.

3. Effectiveness for Small Datasets:

Selection Sort performs well on small datasets where its inefficiencies in terms of comparisons and swaps do not significantly impact performance. For cases where simplicity and low memory usage are prioritized over speed, this algorithm is suitable.

While Selection Sort has its advantages, it also comes with certain drawbacks that make it less suitable for other situations. Here are some of the key disadvantages of using this sorting algorithm:

1. Inefficiency for Large Datasets:

Selection Sort has a time complexity of O(n^2) in all cases—best, average, and worst. This quadratic time complexity means that its performance reduces rapidly as the size of the dataset increases which makes it unsuitable for sorting large datasets.

2. Lack of Stability:

Selection Sort is not a stable sorting algorithm. Stability refers to maintaining the close order of elements with equal keys. Since the algorithm swaps elements, it can disturb the original order of identical elements, which can be undesirable in certain applications.

3. Non-Adaptive Nature:

The algorithm performs the same number of comparisons and swaps still of the initial arrangement of elements. This non-adaptive behavior makes it inefficient for datasets that are already sorted or entirely sorted.

Selection Sort is useful in specific contexts where its simplicity and characteristics are beneficial. Here are some common applications where this algorithm can be effectively used:

1. Educational Purposes:

Selection Sort is taught in computer science courses to introduce sorting algorithms. Its simplicity helps students hold fundamental concepts like comparison, swapping, and algorithmic analysis. 

2. Small Datasets:

In scenarios where datasets are small, the overhead of more complex algorithms does not justify their use. Selection Sort’s simplicity and ease of implementation make it ideal for sorting small collections where performance is not a critical factor.

3. Memory-Constrained Environments:

Since Selection Sort has a space complexity of O(1), it is particularly useful in environments where memory resources are limited. For embedded systems or low-memory devices, its low-memory requirements outweigh its inefficiency for larger datasets.

Selection Sort is an excellent starting point for understanding sorting algorithms. It acts as a foundation for more advanced techniques. By implementing Selection sorting in various ways, such as iterative and recursive methods, programmers can learn about algorithm design and optimization.

1. What is the concept of selection sort?

Selection Sort is a simple sorting algorithm that repeatedly finds the smallest (or largest) element in the unsorted portion of the list and swaps it with the first unsorted element. This process continues until the entire list is sorted.

2. What is the introduction of sorting in C?

Sorting in C refers to arranging elements of an array or list in a specific order (ascending or descending). It can be implemented using algorithms like Bubble Sort, Selection Sort, Merge Sort, and QuickSort, either manually or using built-in libraries.

3. What are the advantages of selection sort?

Selection Sort is simple to implement, works well on small datasets, and doesn't require extra memory for sorting. It is also useful when memory writes are costly, as it minimizes the number of swaps.

4. What is the time complexity of selection sort?

The time complexity of Selection Sort is O(n^2) for both best and worst cases, as it involves nested loops to find the minimum element and perform swaps.

5. When should you use selection sort?

Selection Sort is best used for small datasets or when minimizing memory writes is required, such as in systems with limited resources or flash memory devices.

6. What are the key characteristics of selection sort?

Selection Sort is an in-place, comparison-based algorithm that is not adaptive or stable by default. It performs well on small datasets but is inefficient for large ones.

7. How does the selection sort algorithm work step by step?

Selection Sort works by dividing the array into two parts: sorted and unsorted. It repeatedly finds the smallest element in the unsorted part and swaps it with the first unsorted element in the sorted portion.