C Program For Selection Sort Algorithm In Data Structure

Sorting is a fundamental operation in computer science, crucial for organizing data efficiently. In this article, you will learn about the Selection Sort algorithm, a straightforward comparison-based sorting technique, including its step-by-step implementation in C.

Problem Statement

The core problem is to arrange a given list of elements (e.g., numbers, characters) in a specific order, such as ascending or descending. An unsorted array makes searching, merging, and other data processing tasks significantly slower and more complex. Efficient sorting algorithms are vital for optimizing these operations.

Example

Consider an unsorted array: [64, 25, 12, 22, 11]. Let's trace how Selection Sort would arrange it in ascending order:

• Initial Array: [64, 25, 12, 22, 11]
• Pass 1: Find the minimum element in [64, 25, 12, 22, 11] (which is 11). Swap 11 with 64.
• Array after Pass 1: [11, 25, 12, 22, 64]
• Pass 2: Find the minimum element in [25, 12, 22, 64] (which is 12). Swap 12 with 25.
• Array after Pass 2: [11, 12, 25, 22, 64]
• Pass 3: Find the minimum element in [25, 22, 64] (which is 22). Swap 22 with 25.
• Array after Pass 3: [11, 12, 22, 25, 64]
• Pass 4: Find the minimum element in [25, 64] (which is 25). Swap 25 with 25 (no change).
• Array after Pass 4: [11, 12, 22, 25, 64]
• Sorted Array: [11, 12, 22, 25, 64]

Background & Knowledge Prerequisites

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

• C Programming Basics: Variables, data types, operators.
• Arrays: Declaring, initializing, and accessing elements.
• Loops: for loops for iteration.
• Functions: Defining and calling functions.
• Pointers (optional but helpful for understanding swap): Although not strictly necessary for a basic swap, it's good to know how they work.

Use Cases or Case Studies

While not the most efficient algorithm for large datasets, Selection Sort has specific applications where its characteristics are beneficial:

• Small Datasets: For very small arrays (e.g., less than 20 elements), its simplicity and ease of implementation make it a viable choice.
• Minimizing Swaps: Selection Sort performs a maximum of N-1 swaps (where N is the number of elements), regardless of the initial order. This can be advantageous in scenarios where memory write operations are significantly more expensive than comparisons.
• Educational Purposes: It's an excellent introductory sorting algorithm due to its straightforward logic, making it easy to understand fundamental sorting concepts.
• In-place Sorting Requirement: It is an in-place sorting algorithm, meaning it doesn't require extra memory proportional to the input size beyond a few temporary variables.

Solution Approaches

Selection Sort Algorithm

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

// Selection Sort Algorithm
#include <stdio.h>

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

// 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");
}

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

    // Step 1: Traverse through all array elements
    for (i = 0; i < n - 1; i++) {
        // Step 2: 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;
            }
        }

        // Step 3: Swap the found minimum element with the first element
        // of the unsorted part (at index 'i')
        swap(&arr[min_idx], &arr[i]);

        printf("Array after pass %d: ", i + 1);
        printArray(arr, n);
    }
}

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

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

    // Step 2: Apply selection sort
    selectionSort(arr, n);

    // Step 3: Print the sorted array
    printf("\\nSorted array: ");
    printArray(arr, n);

    return 0;
}

Run

Sample Output

Original array: 64 25 12 22 11 
Array after pass 1: 11 25 12 22 64 
Array after pass 2: 11 12 25 22 64 
Array after pass 3: 11 12 22 25 64 
Array after pass 4: 11 12 22 25 64 

Sorted array: 11 12 22 25 64

Stepwise Explanation

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

• Takes an integer array arr and its n size as input.

1. Outer Loop (for (i = 0; i < n - 1; i++)):

• This loop iterates n-1 times. In each iteration i, it aims to place the correct element at the i-th position.
• The i variable marks the boundary between the sorted (left) and unsorted (right) portions of the array. Initially, the sorted part is empty.

1. Finding the Minimum Element:

• min_idx = i;: Assumes the element at the current position i is the minimum in the unsorted subarray.
• Inner Loop (for (j = i + 1; j < n; j++)): This loop searches the *remaining unsorted portion* of the array (from i+1 to n-1) to find the actual minimum element.
• if (arr[j] < arr[min_idx]): If an element arr[j] is found that is smaller than the current minimum arr[min_idx], then min_idx is updated to j.

1. Swapping Elements:

• After the inner loop completes, min_idx holds the index of the smallest element in the unsorted subarray.
• swap(&arr[min_idx], &arr[i]);: The minimum element (at min_idx) is swapped with the element at the current position i. This moves the smallest element of the unsorted part to its correct position in the sorted part.

1. main() function:

• Initializes an example array arr.
• Calculates its size n.
• Prints the original array.
• Calls selectionSort() to sort the array.
• Prints the sorted array.

Conclusion

Selection Sort is a simple, in-place comparison sorting algorithm that performs consistently regardless of the initial order of elements. It has a time complexity of O(N²) in all cases (best, average, worst) because it always iterates through the entire unsorted portion to find the minimum element. While not efficient for large datasets, its minimal swap count (N-1) can be an advantage when memory write operations are costly, and its ease of understanding makes it a good educational tool.

Summary

• Algorithm Type: Comparison-based, in-place sorting.
• Mechanism: Repeatedly finds the minimum element from the unsorted portion and places it at the correct position.
• Time Complexity: O(N²) for best, average, and worst cases.
• Space Complexity: O(1) (in-place).
• Stability: Unstable (relative order of equal elements may not be preserved).
• Use Cases: Suitable for small datasets or when minimizing data swaps is crucial.