Selection sort
Tags: sortingalgorithms, algorithmanalysis, computerscience, beginners
Published: 2023-08-05 09:09:42

**INTRODUCTION**

Welcome to the world of sorting algorithms! Today, we'll explore a simple and easy-to-understand sorting technique called "Selection Sort."

Imagine you have a list of numbers all mixed up, and you want to arrange them in ascending order from the smallest to the largest. Selection Sort is like a helpful organizer that goes through the list, one by one, and carefully picks the smallest number to put it in the right place.

We'll take a step-by-step journey through this method, and you'll see how it gracefully arranges the numbers into a neat order, just like sorting playing cards in your hand. This algorithm might not be as fancy as some others, but its straightforward approach makes it perfect for learning and smaller lists of numbers.

So, let's dive in and discover the magic of Selection Sort, a simple yet powerful tool to tame the chaos and bring order to our data. Get ready to unlock the secrets of sorting as we walk through the elegant dance of Selection Sort!

**SIMPLE EXAMPLE**

1. Imagine you have a bunch of numbered cards scattered on the table, and you want to arrange them from the smallest to the largest.
2. Start by picking the first card in the pile and say, "This is my chosen card for now."
3. Look at all the other cards left on the table. Find the smallest number among those cards.
4. If you find a card with a smaller number than your chosen card, say, "Oh, I found a smaller card!" and swap it with your chosen card.
5. Now, the card with the smallest number is in your hand, and the old chosen card is on the table.
6. Repeat Steps 2 to 5, but now start with the second card and keep going until you reach the last card.
7. Congratulations! All the cards are now arranged from the smallest to the largest. You sorted the cards using Selection Sort!

In simple terms, Selection Sort works like picking cards one by one, finding the smallest number, and putting it in the right place in your hand. Keep doing this until all the cards are sorted. It's like a game of finding the smallest card and putting it in the correct order.

```cpp
#include <bits/stdc++.h>
using namespace std;

// Function to perform selection sort on an array
void selectionsort(int arr[], int n) {
    // Iterate through the array
    for (int i = 0; i < n - 1; i++) {
        // Assume the current index holds the minimum value
        int min_indx = i;

        // Find the index of the smallest element in the 
        // unsorted part of the array
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[min_indx]) {
                // Update min_indx to point to the new minimum 
                // element
                min_indx = j;
            }
        }

        // Swap the found minimum element with the first 
        // element of the unsorted part
        if (min_indx != i) {
            swap(arr[min_indx], arr[i]);
        }
    }
}

// Function to print the elements of the array
void printsortedarr(int arr[], int n) {
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;

    int arr[n];
    cout << "Enter " << n << " elements: ";
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // Call the selectionsort function to sort the array
    selectionsort(arr, n);

    cout << "After selection sort: " << endl;
    // Print the sorted array
    printsortedarr(arr, n);

    return 0;
}

```

| Property          | Description                                      |
|-------------------|--------------------------------------------------|
| Algorithm Type    | Comparison-based Sorting Algorithm              |
| Time Complexity   | O(n^2)                                           |
| Space Complexity  | O(1)                                             |
| Best Case         | O(n^2)                                           |
| Average Case      | O(n^2)                                           |
| Worst Case        | O(n^2)                                           |
| Adaptive          | Yes                                              |
| Stable            | No                                               |
| In-place          | Yes                                              |
| Sorting Direction | Ascending (Can be modified for descending order) |
| Suitable For      | Small arrays or lists                            |
| Use Cases         | Sorting small data sets, educational purposes, partially sorted data, embedded systems, resource-constrained environments, quick implementation.   |