C Program For Selection Sort Without Function

Selection sort is a straightforward comparison-based sorting algorithm that divides the input list into two parts: a sorted sublist and an unsorted sublist. In this article, you will learn how to implement selection sort in C directly within the main function, without using any additional custom functions.

Problem Statement

The goal is to sort an array of integers in ascending order using the selection sort algorithm. The constraint is to implement the entire sorting logic, including finding the minimum element and swapping, directly within the main function without defining any separate helper functions. This demonstrates a basic, self-contained implementation of the algorithm.

Example

Consider an unsorted array of integers. Applying selection sort will rearrange its elements into ascending order.

• Input Array: [64, 25, 12, 22, 11]
• Output Array (Sorted): [11, 12, 22, 25, 64]

Background & Knowledge Prerequisites

To understand this implementation, readers should be familiar with the following C programming concepts:

• Basic C Syntax: Understanding how to declare variables, use data types, and write simple statements.
• Arrays: Knowledge of how to declare, initialize, and access elements in one-dimensional arrays.
• Loops: Proficiency with for loops for iterating over arrays.
• Conditional Statements: Basic understanding of if statements for comparisons.
• Variable Swapping: The technique to exchange the values of two variables using a temporary variable.

Use Cases or Case Studies

Sorting algorithms like selection sort are fundamental in computer science and have various applications:

• Educational Purpose: Often taught as one of the simplest sorting algorithms to introduce concepts like in-place sorting and time complexity.
• Small Datasets: Efficient enough for sorting small lists or arrays where performance is not a critical concern.
• Data Organization: Used when stable sorting is not required and simple data arrangement is needed, such as arranging student scores or product IDs.
• Finding Min/Max Elements Repeatedly: The core idea of finding the minimum (or maximum) element in a sub-array is reusable in other algorithms.
• Embedded Systems: In resource-constrained environments where simplicity and minimal overhead are prioritized over highly optimized performance for small data.

Solution Approaches

The core idea of selection sort is to repeatedly find the minimum element from the unsorted part of the array and put it at the beginning of the unsorted part.

In-place Selection Sort within main

This approach implements the entire selection sort logic directly inside the main function. It uses nested loops to traverse the array, find the minimum element in the remaining unsorted portion, and swap it with the element at the current position of the outer loop.

// Selection Sort without Function
#include <stdio.h>

int main() {
    // Step 1: Declare and initialize the array
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]); // Calculate the number of elements

    // Step 2: Print the original array
    printf("Original array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    // Step 3: Implement Selection Sort logic
    // One by one, move the boundary of the unsorted subarray
    for (int i = 0; i < n - 1; i++) {
        // Find the minimum element in the unsorted array
        int min_idx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }

        // Swap the found minimum element with the first element of the unsorted subarray
        // This is done without a separate swap function
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }

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

    return 0;
}

Run

Sample Output:

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

Stepwise Explanation for Clarity:

1. Initialization: An integer array arr is declared and initialized with unsorted values. The variable n calculates the number of elements in the array.
2. Outer Loop (for (int i = 0; i < n - 1; i++)): This loop iterates from the first element up to the second-to-last element. The i variable marks the current position where the smallest element found in the unsorted part will be placed. We iterate up to n-1 because if the first n-1 elements are sorted, the last element must also be in its correct place.
3. Finding Minimum (int min_idx = i; and inner loop):

• min_idx is initialized to i. This assumes the element at the current position i is the minimum initially in the unsorted subarray.
• The inner loop (for (int j = i + 1; j < n; j++)) starts from i + 1 (the next element after i) and iterates through the rest of the unsorted part of the array.
• Inside the inner loop, if (arr[j] < arr[min_idx]) compares the current element arr[j] with the element currently considered minimum (arr[min_idx]). If arr[j] is smaller, min_idx is updated to j. This ensures min_idx always holds the index of the smallest element found so far in the unsorted part.

1. Swapping Elements: After the inner loop completes, min_idx holds the index of the smallest element in the unsorted subarray (from i to n-1).

• The elements at arr[min_idx] and arr[i] are swapped using a temporary variable temp. This moves the smallest element to its correct sorted position at arr[i].

1. Iteration: The outer loop continues, moving the boundary i one step further, effectively extending the sorted sublist by one element and reducing the unsorted sublist.
2. Output: After the outer loop finishes, the entire array is sorted, and its contents are printed.

Conclusion

Implementing selection sort directly within the main function in C is a clear demonstration of its core logic. This approach, while basic, highlights how to find the minimum element in an unsorted portion of an array and move it to its correct sorted position using nested loops and in-place swapping, without relying on additional user-defined functions.

Summary

• Selection Sort Core: Repeatedly finds the minimum element from the unsorted part and places it at the correct position.
• In-place Implementation: The entire sorting logic, including finding the minimum index and swapping elements, is contained within the main function.
• Nested Loops: An outer loop iterates through the array to mark the current sorted boundary, and an inner loop finds the minimum element in the remaining unsorted portion.
• Direct Swapping: Elements are swapped using a temporary variable, explicitly written within the main function.
• Simplicity: This method is straightforward and effective for small datasets or for learning purposes.