Sorting Algorithms: Selection Sort in C

What You’ll Learn 📚

• Understand the core concepts of Selection Sort
• Key terminology explained in a friendly way
• Step-by-step examples from simple to complex
• Common questions and answers
• Troubleshooting common issues

Introduction to Selection Sort

Selection Sort is one of the simplest sorting algorithms. It works by repeatedly finding the minimum element from the unsorted part of the array and putting it at the beginning. Imagine sorting a deck of cards by selecting the smallest card and moving it to the front each time. Easy, right? Let’s break it down further.

Key Terminology

• Array: A collection of items stored at contiguous memory locations.
• Unsorted Part: The portion of the array that hasn’t been sorted yet.
• Sorted Part: The portion of the array that has been sorted.

Simple Example

#include <stdio.h>
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i;
        for (int j = i+1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
void printArray(int arr[], int size) {
    for (int i=0; i < size; 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: \n");
    printArray(arr, n);
    return 0;
}

Sorted array: 
11 12 22 25 64 

Progressively Complex Examples

Example 1: Sorting a Larger Array

// Code for sorting a larger array

// Expected output for larger array

Example 2: Sorting with Duplicate Values

// Code for sorting with duplicate values

// Expected output for array with duplicates

Example 3: Sorting in Descending Order

// Code for sorting in descending order

// Expected output for descending order

Common Questions and Answers

1. What is the time complexity of Selection Sort?

   The time complexity is O(n^2) because of the nested loops.

2. Why is it called Selection Sort?

   Because it repeatedly selects the smallest element from the unsorted part and moves it to the front.

3. Is Selection Sort stable?

   No, it is not stable because it may change the relative order of equal elements.

Troubleshooting Common Issues

Make sure your array indices are correct to avoid out-of-bounds errors.

If your program isn’t sorting correctly, check the logic inside your loops. Ensure you’re swapping elements properly.

Practice Exercises

• Try sorting an array of strings using Selection Sort.
• Modify the algorithm to sort in descending order.

Remember, practice makes perfect! Keep experimenting and soon you’ll have your own lightbulb moments. 💡

For more resources, check out the C Language Reference.