Sorting Made Easy: Understanding Selection Sort

Introduction

Sorting data is like arranging books on a shelf so you can find them easily. One simple way to do this with numbers is called Selection Sort. Let's explore how Selection Sort works and why it's useful.

What is Selection Sort?

Selection Sort is like finding the smallest number in a jumbled pile of numbers and putting it in its correct spot. You repeat this process until all the numbers are in order.

How Does Selection Sort Work?

Lets consider the following array as an example: arr[] = {64, 25, 12, 22, 11}

First pass:

• For the first position in the sorted array, the whole array is traversed from index 0 to 4 sequentially. The first position where 64 is stored presently, after traversing whole array it is clear that 11 is the lowest value.
• Thus, replace 64 with 11. After one iteration 11, which happens to be the least value in the array, tends to appear in the first position of the sorted list 

Second Pass:

• For the second position, where 25 is present, again traverse the rest of the array in a sequential manner.
• After traversing, we found that 12 is the second lowest value in the array and it should appear at the second place in the array, thus swap these values.

Third Pass:

• Now, for third place, where 25 is present again traverse the rest of the array and find the third least value present in the array.
• While traversing, 22 came out to be the third least value and it should appear at the third place in the array, thus swap 22 with element present at third position.

Fourth pass:

• Similarly, for fourth position traverse the rest of the array and find the fourth least element in the array 
• As 25 is the 4th lowest value hence, it will place at the fourth position.

Fifth Pass:

• At last the largest value present in the array automatically get placed at the last position in the array
• The resulted array is the sorted array.

Let's See It in Action:

Here's a simple program that uses Selection Sort to sort a list of numbers:

#include <stdio.h>

// Function to print the elements of an array
void printarray(int* A, int n){
    for(int i = 0; i < n; i++){
        printf("%d ", A[i]); // Print each element of the array
    }
    printf("\n"); // Move to the next line after printing all elements
}

// Function to sort an array using the selection sort algorithm
void selectionsort(int* A, int n){
    int indexofmin, temp; 

    for(int i = 0; i < n - 1; i++){ 
        indexofmin = i; // Initialize indexofmin to the current index
        
        for(int j = i + 1; j < n; j++){
            if(A[j] < A[indexofmin]){ // Compare with the minimum element found so far
                indexofmin = j; // Update indexofmin if a smaller element is found
            }
        }
        
        // Swap A[i] with the minimum element found
        temp = A[i];
        A[i] = A[indexofmin];
        A[indexofmin] = temp;
    }
}

// Main function
int main(){
    int A[] = {12, 54, 65, 7, 23, 9}; // Declare and initialize an integer array
    int n = 6; // Number of elements in the array

    // Print the array before sorting
    printf("The array before sorting: ");
    printarray(A, n);

    // Sort the array using the selection sort algorithm
    selectionsort(A, n);

    // Print the array after sorting
    printf("The array after sorting: ");
    printarray(A, n);

    return 0; // Return 0 to indicate successful execution
}

Conclusion:
Selection Sort might not be the fastest way to sort a lot of numbers, but it's a great way to understand how sorting works. Plus, for small lists, it gets the job done just fine. So, the next time you need to sort some numbers, give Selection Sort a try!