C Program For Selection Sort In Ascending Order

Sorting data is a fundamental operation in computer science, crucial for organizing information efficiently. In this article, you will learn how to implement the selection sort algorithm in C to arrange elements in ascending order.

Problem Statement

Efficiently organizing data is crucial for various applications, from database management to search algorithms. The challenge is to rearrange an unsorted list of elements into a specific order, such as ascending or descending, using a straightforward and understandable algorithm. For large datasets, the choice of sorting algorithm significantly impacts performance.

Example

Consider the following unsorted array of integers:

Original array: [64, 25, 12, 22, 11]

After applying selection sort in ascending order, the array becomes:

Sorted array: [11, 12, 22, 25, 64]

Background & Knowledge Prerequisites

To understand this article, readers should have a basic grasp of:

• C Programming Basics: Understanding variables, data types, and fundamental syntax.
• Arrays: How to declare, initialize, and access elements in a C array.
• Loops: Familiarity with for loops for iteration.
• Conditional Statements: Knowledge of if statements for comparisons.
• Functions: Basic understanding of defining and calling functions.

Use Cases or Case Studies

Sorting algorithms like selection sort are foundational and find application in many areas:

• Data Organization: Arranging records in databases (e.g., sorting by name, ID, or date) for quicker retrieval and display.
• Search Algorithms: Preparing data for more efficient searching techniques like binary search, which requires sorted input.
• User Interface Displays: Presenting lists of items (e.g., products, contacts, scores) in an ordered manner for better user experience.
• Ranking Systems: Sorting scores or performance metrics to determine top performers or rank entities.
• Small Data Sets: For very small arrays, its simplicity can make it a viable, easy-to-implement option, although less efficient than others for larger sets.

Solution Approaches

Implementing Selection Sort in C

Selection sort works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning.

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

// Function to swap two elements
void swap(int* xp, int* yp) {
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

// Function to perform selection sort on an array
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]);
    }
}

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

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

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

    // Step 3: Call the selection sort function
    selectionSort(arr, n);

    // Step 4: Print the sorted array
    printf("Sorted array: \\n");
    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. swap Function: This helper function takes two integer pointers and swaps their values. This is a common utility for many sorting algorithms.
2. selectionSort Function:

• It takes an integer array arr and its size (n) as input.
• The outer for loop (for (i = 0; i < n - 1; i++)) iterates from the first element up to the second-to-last element. In each iteration i, it considers the subarray from arr[i] to arr[n-1] as the unsorted part.
• min_idx is initialized to i. This variable will store the index of the smallest element found so far in the current unsorted subarray.
• The inner for loop (for (j = i + 1; j < n; j++)) iterates through the unsorted part (from i + 1 to n - 1) to find the actual minimum element.
• If an element arr[j] is found to be smaller than arr[min_idx], min_idx is updated to j.
• After the inner loop completes, min_idx holds the index of the smallest element in the unsorted subarray.
• The swap function is then called to exchange the element at arr[min_idx] (the smallest element) with the element at arr[i] (the first element of the current unsorted subarray). This places the smallest element in its correct sorted position.

1. printArray Function: A utility function to display the contents of an array, which is useful for observing the array before and after sorting.
2. main Function:

• An example array arr is initialized.
• The sizeof operator is used to calculate the number of elements n in the array.
• The original array is printed.
• The selectionSort function is called to sort the array.
• The sorted array is then printed.

Conclusion

Selection sort is a simple, in-place comparison sorting algorithm that is easy to understand and implement. It performs well on small datasets due to its minimal number of swaps. While its time complexity is O(n^2) in all cases, making it less efficient for large datasets compared to algorithms like merge sort or quicksort, its simplicity makes it a good starting point for learning about sorting algorithms.

Summary

• Algorithm: Selection sort repeatedly finds the minimum element from the unsorted portion of the array and places it at the correct position.
• Process: It divides the array into two parts: a sorted subarray and an unsorted subarray. In each step, it selects the smallest element from the unsorted part and moves it to the sorted part.
• In-Place: It sorts the array without requiring extra space (O(1) auxiliary space complexity).
• Time Complexity: O(n^2) in the best, average, and worst-case scenarios, where 'n' is the number of elements. This is due to the nested loops always iterating through all elements.
• Stability: Selection sort is generally not a stable sorting algorithm, meaning the relative order of equal elements might not be preserved.
• Swaps: It performs a minimal number of swaps (exactly n-1 swaps), which can be advantageous in scenarios where writes to memory are costly.