Selection Sort Implementation in CPP

1. Introduction

Selection Sort is a simple comparison-based sorting algorithm. The core idea behind Selection Sort is dividing the input list into two parts: a sorted sublist and an unsorted sublist. The algorithm repeatedly selects the smallest (or largest, if you're sorting in descending order) element from the unsorted sublist and moves it to the end of the sorted sublist, until the unsorted sublist is empty.

2. Implementation Steps

1. Start with the first position as the current minimum.

2. Compare this current minimum with the next item until you find a smaller number.

3. If a smaller number is found, designate it as the new minimum and continue until the end of the array.

4. Swap the two values: the first value and the smallest value found.

5. Move to the next position and repeat the steps.

3. Implementation in C++ Programming

#include<iostream>
void selectionSort(int arr[], int n) {
    for (int i = 0; i < n-1; i++) {
        int min_idx = i; // 1. Start with current index as minimum
        for (int j = i+1; j < n; j++) {
            // 2. and 3. If a smaller number is found, update the minimum index
            if (arr[j] < arr[min_idx]) {
                min_idx = j;
            }
        }
        // 4. Swap the found minimum with the first element
        int temp = arr[min_idx];
        arr[min_idx] = arr[i];
        arr[i] = temp;
    }
}
int main() {
    int arr[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    std::cout << "Sorted array: \n";
    for (int i = 0; i < n; i++) {
        std::cout << arr[i] << " ";
    }
    std::cout << std::endl;
    return 0;
}

Output:

Sorted array:
11 12 22 25 64

Explanation:

1. int min_idx = i;: We start with the first element as the minimum for each iteration.

2. if (arr[j] < arr[min_idx]): As we loop through the array if we find a number smaller than our current minimum, we update min_idx to the current index.

3. This comparison continues until the end of the array, ensuring we've found the absolute minimum.

4. Once we've found the smallest item in the unsorted portion, we swap it with the first item in the unsorted portion, effectively growing the sorted portion and shrinking the unsorted portion by one item each time.

5. The process then repeats for the next position until the entire array is sorted.