Introduction to Selection Sort Algorithm

Selection Sort Algorithm Walkthrough
🔗
Selection Sort Detailed Explanation
🔗
Selection Sort Algorithmic Dance
🔗
Click here to suggest a better video or view suggestions..

Have you ever noticed how you naturally sort small items, such as arranging books by height or organizing toys by size? You will probably find the smallest item first, set it aside, then look for the next smallest item, set it aside, and repeat the same process until you pick all the items. Selection sort is an algorithm that works exactly similar to this natural sorting process. It’s one of the most intuitive sorting methods in computer science because it mimics how humans often sort things in real life. Before we get into the technical details, let’s first understand what sorting is all about and why it’s so crucial in computer science.

What is Sorting?

Sorting refers to the process of organizing data in a specific order, which could be either ascending (from smallest to largest) or descending (from largest to smallest). Think about it – you see sorted data all around you every day!

  • Imagine a contact list on your phone, where names are arranged in alphabetical order.
  • Consider a list of products on a shopping website, sorted from the lowest price to the highest.
  • Think about a teacher arranging student grades from highest to lowest.
  • Or a calendar app displaying your events in chronological order.

Sorting makes it much easier to find, understand, and use information. For instance, it’s way quicker to find someone’s name in a phone book if the names are sorted alphabetically, rather than having to check every single entry. Sorting is fundamental to many things we do with computers, making tasks like searching and analyzing data much more efficient.

What is Selection Sort Algorithm?

Selection sort is a sorting algorithm that works by repeatedly picking the smallest item from a collection and putting it next to the previous smallest, and repeating this until everything is in order.

Imagine you need to arrange books on a shelf from shortest to tallest. The sequence of actions explained below is one way of doing it:

  1. Look through all the books and find the shortest one.
  2. Put that shortest book at the far left of the shelf.
  3. Now, from the remaining books, find the next shortest.
  4. Place that book right next to the first one.
  5. Keep doing this until all your books are in the right order.

That’s essentially what selection sort does! Visually, as the algorithm runs, it divides the list into two parts:

  • A sorted portion on the left side, which grows with each step.
  • An unsorted portion on the right side, which shrinks as elements are moved into their correct positions.

Walkthrough of Selection Sort Algorithm

Let’s walk through how selection sort works using an example. Imagine we have this list of numbers that we want to sort from smallest to largest: [64, 34, 25, 12, 22]

Here’s how selection sort will handle it:

  1. First Pass:

    • We start by looking through the entire list [64, 34, 25, 12, 22] to find the smallest number. We find 12.
    • Now, we swap 12 with the first element in the list, which is 64.
    • The list now looks like this: [12 | 34, 25, 64, 22]. The | symbol separates the sorted part (on the left) from the unsorted part (on the right).

  2. Second Pass:

    • Next, we look at the unsorted part of the list [34, 25, 64, 22] and find the smallest number there. It’s 22.
    • We swap 22 with the first element in the unsorted part, which is 34.
    • The list becomes: [12, 22 | 25, 64, 34]

  3. Third Pass:

    • Now we focus on the unsorted part [25, 64, 34]. The smallest number is 25.
    • Since 25 is already in the correct position, we don’t need to swap anything.
    • The list remains: [12, 22, 25 | 64, 34]

  4. Fourth Pass:

    • Looking at the unsorted part [64, 34], we find that 34 is the smallest.
    • We swap 34 with 64.
    • The list is now: [12, 22, 25, 34 | 64]

  5. Final Pass:

    • Only one element is left in the unsorted part: 64.
    • Since there’s nothing to compare it to, it is already in its correct position.
    • The final sorted list is: [12, 22, 25, 34, 64]

Key Characteristics

  • In-Place Algorithm: Selection sort performs all operations directly within the original array, requiring only O(1) extra space. It achieves this by swapping elements within the array without needing additional storage structures.

  • Simplicity: The algorithm is straightforward to understand and implement, making it an excellent choice for educational purposes and small datasets.

  • Unstable Sort: Basic version of selection sort is unstable, meaning it may change the relative order of equal elements. However, it can be modified to be stable if needed.

  • Comparison-Based: The algorithm makes decisions by comparing elements, making it work with any data type that can be compared.

  • Non-Adaptive: Whether the input array is nearly sorted or completely random, selection sort goes through the same steps, making it non-adaptive.

What’s Next?

Now that you understand the basics of selection sort, you might want to: