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

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.

Pseudo Code

SelectionSort(arr, n)

FOR i ← 0 TO n - 2
    minIndex ← i

    FOR j ← i + 1 TO n - 1
        IF arr[j] < arr[minIndex]
            minIndex ← j
        END IF
    END FOR

    SWAP arr[i] WITH arr[minIndex]
END FOR

RETURN arr

C Program for Selection Sort

Here is the 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;
}

Output

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

Explanation of the Code

This Selection Sort code in C arranges elements in ascending order by repeatedly finding the smallest value from the unsorted portion of the array and placing it in the correct position. The selectionSort() function performs the sorting by comparing elements and swapping them when needed. The printArray() function displays the array contents before and after sorting. In the main() function, an array of integers is initialized, its size is calculated, and the sorting function is called. After execution, the original array is transformed into a sorted array, showing the working of the Selection Sort algorithm.

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 C program for 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 is a 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 in C language 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.

A C Program for 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 of Selection Sort code in C using Functions:

#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 C

In Selection Sort code in C, 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 a C Program for 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

Selection Sort can be implemented directly inside the main() function without creating a separate sorting function. The algorithm works by dividing the array into sorted and unsorted sections. During each pass, it finds the smallest element in the unsorted portion and swaps it with the first unsorted element. This process continues until the entire array is sorted.

Implementing Selection Sort in C without function is useful for beginners because all the sorting logic remains in one place, making it easier to follow the execution flow. However, for larger programs, using separate functions is generally preferred because it improves code organization, readability, and reusability.

Code Example

#include <stdio.h>

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

   for (int i = 0; i < n - 1; i++) {
       int minIndex = i;

       for (int j = i + 1; j < n; j++) {
           if (arr[j] < arr[minIndex]) {
               minIndex = j;
           }
       }

       int temp = arr[i];
       arr[i] = arr[minIndex];
       arr[minIndex] = temp;
   }

   printf("Sorted Array: ");

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

   return 0;
}

Output

Sorted Array: 11 12 22 25 64

Explanation

The program starts by selecting the first element as the minimum value. It then compares this value with the remaining elements to find the actual smallest element. After identifying the smallest value, a swap is performed. The same process is repeated for the remaining unsorted elements until the array is completely sorted in ascending order.

A while loop can also be used to implement Selection Sort in C 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. Selection Sort follows a straightforward approach of finding the smallest element and placing it in the correct position. Its simple logic makes it one of the easiest sorting algorithms for beginners to understand.
2. The algorithm sorts elements within the original array and does not need additional storage. This gives it a space complexity of O(1), making it suitable for memory-limited environments.
3. Unlike some sorting algorithms that swap elements frequently, Selection Sort performs at most one swap during each pass. This can be beneficial when write operations are costly.
4. The algorithm follows the same sequence of operations regardless of the input arrangement. This predictable behavior can be useful in situations where consistent execution patterns are preferred.
5. When working with small datasets, Selection Sort can provide acceptable performance while keeping the implementation simple and easy to maintain.

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. Selection Sort has a time complexity of O(n²), causing execution time to increase significantly as the number of elements grows.
2. Equal elements may change their original order during swapping. This can create issues in applications where maintaining the initial sequence of identical values is important.
3. Even if the array is already sorted or nearly sorted, the algorithm still performs the same number of comparisons, leading to unnecessary work.
4. To locate the minimum element during each pass, Selection Sort compares many elements repeatedly, which reduces efficiency compared to more advanced sorting methods.
5. Modern applications typically prefer algorithms such as Quick Sort, Merge Sort, or Heap Sort because they offer significantly better performance on medium and large datasets.

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

A common real-world application of Selection Sort in C is organizing product prices in a small store. Suppose a shop owner wants to display products from the lowest price to the highest price. Selection Sort can repeatedly find the cheapest product from the unsorted list and place it in its correct position until all prices are arranged in order.

C Program: Sorting Product Prices Using Selection Sort

#include <stdio.h>

int main() {
    int prices[] = {450, 120, 300, 200, 150};
    int n = sizeof(prices) / sizeof(prices[0]);

    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;

        for (int j = i + 1; j < n; j++) {
            if (prices[j] < prices[minIndex]) {
                minIndex = j;
            }
        }

        int temp = prices[i];
        prices[i] = prices[minIndex];
        prices[minIndex] = temp;
    }

    printf("Sorted Product Prices:\n");

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

    return 0;
}

Output

Sorted Product Prices:
120 150 200 300 450

Explanation

In this example, the program sorts product prices in ascending order using Selection Sort in C. During each pass, it identifies the smallest price from the unsorted portion of the array and swaps it with the current position. This process continues until all prices are arranged from lowest to highest, making the list easier to read and analyze.

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. Can you explain Selection Sort with an example?

Selection Sort in C works by repeatedly finding the smallest element from the unsorted portion of an array and placing it in its correct position. For example, in the array {64, 25, 12, 22, 11}, the algorithm first selects 11 and swaps it with 64. It then selects 12, followed by 22, and continues this process until the array becomes {11, 12, 22, 25, 64}. This method is simple to understand but is most suitable for small datasets.

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 algorithm?

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 algorithm 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 algorithm?

Selection Sort in data structure 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 algorithm in C 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.