An Introduction to Selection Sort

This blog post is a continuation of a series of blog posts about Algorithms, as it has been a hard concept for me to grasp as a programmer. Feel to check out the first blogpost about Algorithms, where I provide an introduction of what Algorithms are and an example of an algorithm and the second blog post about Data Structures, where I explained what are Data Structures and what are some types of Data Structures. Also check out the third blog post about Time Complexity and Space Complexity, which I provide an explanation of Time and Space Complexity. I have also written a blog post about Big O Notation. Recently I have written blog posts about Binary Search, Linear Search, Interpolation Search, and Sorting Algorithms.

This blog post I will focus on Selection Sort. I will explain what is Selection Sort, how is Selection Sort associated with Algorithms, try to break down the concept of Selection Sort step by step and provide an example.

What is Selection Sort and how is it associated with Algorithms?

Selection Sort is a type of sorting algorithm. A sorting algorithm is a method for reorganizing a large number of items into a specific order, such as alphabetical, highest-to-lowest value or shortest-to-longest distance. Sorting algorithms take lists of items as input data, perform specific operations on those lists and deliver ordered arrays as output. Applications of sorting algorithms include organizing items by price on a retail website and determining the order of sites on a search engine results page.

Selection sort is a simple sorting algorithm. This sorting algorithm is an in-place comparison-based algorithm in which the list is divided into two parts, the sorted part at the left end and the unsorted part at the right end. Initially, the sorted part is empty and the unsorted part is the entire list.

The smallest element is selected from the unsorted array and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues moving unsorted array boundary by one element to the right.

Sorting Algorithms: Steps on how it works:

1. Iterate over the unsorted array, keeping track of the minimum value as you go.
2. When you get to the end of the array, you know which element is the minimum.
3. Swap the minimum element and the first element in the unsorted array.
4. The first element is now considered sorted.
5. Repeat until the rest of the array is sorted.

Below I have an animation of Selection Sort:

And an image of Selection Sort as well:

Selection Sort: An example

Here is an example of writing the Selection Sort Algorithm based on the steps I provided earlier. Below I have written a function, which accept the following parameters: an array. The function returns the sorted array.

Regarding Time Complexity in Selection Sort, the best and worst case are the same. No matter what, selection sort has a time complexity of O(N²).

And what about Space Complexity in selection sort, it only requires 1 extra temporary variable. O(1)

Overall Selection Sort is an important concept to understand when it comes to algorithms. Thank you for reading this blog post. In upcoming blog posts of this series, I will go over sorting algorithms.