C Program Of Simple Selection Sort Implementation Using Array Ascending Order

Sorting an array of elements is a fundamental operation in computer science, crucial for organizing data efficiently. In this article, you will learn how to implement the Selection Sort algorithm in C to arrange an array of integers in ascending order.

Problem Statement

Efficiently arranging data in a specific order, such as ascending or descending, is a common requirement in many applications. For an unsorted array of numbers, the challenge is to devise a systematic method that places each element in its correct sorted position without disrupting the relative order of other elements.

Example

Consider an unsorted array: [64, 25, 12, 22, 11]

After applying Selection Sort for ascending order, the array should become: [11, 12, 22, 25, 64]

Background & Knowledge Prerequisites

To understand and implement Selection Sort in C, readers should be familiar with:

• C Language Basics: Variables, data types, and fundamental input/output operations.
• Arrays: Declaring, initializing, and accessing elements in one-dimensional arrays.
• Loops: for loops for iterating through array elements.
• Conditional Statements: if statements for comparisons.
• Functions: Defining and calling functions for modular code.

Use Cases or Case Studies

Sorting algorithms like Selection Sort are applied in various scenarios:

• Database Management: Arranging records based on keys (e.g., sorting customers by last name or product by price).
• Search Algorithms: Many efficient search algorithms (like binary search) require data to be sorted first.
• Data Visualization: Presenting data in a meaningful order for easier analysis and understanding.
• Scheduling Tasks: Prioritizing tasks based on urgency or deadline.
• Educational Tools: Demonstrating basic sorting concepts for computer science students.

Solution Approaches

Selection Sort is a straightforward comparison-based sorting algorithm. It works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

Simple Selection Sort in C

This approach systematically finds the smallest element in the unsorted portion of the array and swaps it with the element at the current position, effectively building the sorted array one element at a time from left to right.

// Selection Sort in C (Ascending Order)
#include <stdio.h>

// Function to swap two integers
void swap(int *xp, int *yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = 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");
}

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

    // One by one move boundary of unsorted subarray
    for (i = 0; i < n - 1; i++) {
        // Find the minimum element in unsorted array
        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
        // of the unsorted subarray (at index 'i')
        swap(&arr[min_idx], &arr[i]);
    }
}

int main() {
    // Step 1: Initialize an array
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);

    // Step 2: Print the original array
    printf("Original array: ");
    printArray(arr, n);

    // Step 3: Perform selection sort
    selectionSort(arr, n);

    // Step 4: Print the sorted array
    printf("Sorted array: ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output

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

Stepwise Explanation

1. selectionSort(int arr[], int n) Function:

• This function takes an integer array arr and its n as input.
• Outer Loop (for (i = 0; i < n - 1; i++)): This loop iterates from the first element up to the second-to-last element of the array. The i variable marks the current position where the smallest element found so far in the unsorted subarray will be placed. After each iteration, the element at index i is correctly sorted.
• Finding the Minimum Element (min_idx = i; for (j = i + 1; j < n; j++)): Inside the outer loop, min_idx is initialized to i. The inner loop then iterates from i + 1 to the end of the array (n).
• It compares arr[j] with arr[min_idx]. If arr[j] is smaller, it means a new minimum element has been found, so min_idx is updated to j.
• Swapping Elements (swap(&arr[min_idx], &arr[i])): After the inner loop completes, min_idx holds the index of the smallest element in the unsorted subarray arr[i...n-1]. The swap function is then called to exchange the element at min_idx with the element at the current position i. This places the smallest element found into its correct sorted position.

1. swap(int *xp, int *yp) Function: A helper function that takes two integer pointers and swaps their values.
2. printArray(int arr[], int size) Function: Another helper function to display the contents of the array.
3. main() Function:

• An example array arr is initialized.
• The size n of the array is calculated.
• The original array is printed.
• selectionSort() is called to sort the array.
• The sorted array is then printed.

Conclusion

Selection Sort provides a clear and intuitive way to sort an array. Its core idea is simple: find the minimum element in the unsorted part and place it at the beginning of that part. While not the most efficient for very large datasets due to its O(n^2) time complexity, it is easy to understand and implement, making it a good choice for smaller arrays or as an educational tool.

Summary

• Algorithm Goal: Sorts an array by repeatedly finding the minimum element from the unsorted part and moving it to the sorted part.
• Process: An outer loop iterates through the array, and an inner loop finds the minimum element in the remaining unsorted subarray.
• Swapping: The minimum element is swapped with the element at the current position of the outer loop.
• Simplicity: Easy to implement and understand.
• Time Complexity: O(n^2) in all cases (best, average, worst), making it less suitable for very large datasets compared to more advanced sorting algorithms.
• Space Complexity: O(1), as it sorts in-place without requiring additional memory proportional to the input size.