Selection Sort, Bubble Sort, and Insertion Sort

Get an overview of basic sorting algorithms like selection sort, bubble sort, and insertion sort.

We'll cover the following

What is sorting?

Sorting is any process of arranging items systematically. In computer science, sorting algorithms put elements of a list in a certain order.

The most frequently used orders are numerical (according to numbers) and lexicographical (according to letters). Efficient sorting is important for optimizing the efficiency of other algorithms, which require sorted input or the sort of a given input as part of their process.

Formal definition

A list or array is sorted in ascending order if ∀\forall ii, such that i≤n−1i \leq n-1, A[i]≤A[i+1]A[i]\leq A[i+1]. Similarly, a list or array is sorted in descending order if ∀\forall ii, such that i≤n−1i \leq n-1, A[i]≥A[i+1]A[i]\geq A[i+1].

Sorting algorithms

Let’s discuss a few sorting algorithms:

Selection sort

This algorithm works by repeatedly finding the minimum element in the list and placing it at the beginning. This way, the algorithm maintains two lists:

  1. The sublist of already-sorted elements, which is filled from left to right.
  2. The sublist of the remaining unsorted elements that need to be sorted.

In other words, this algorithm works by iterating over the list and swapping each element with the minimum (or maximum) element found in the unsorted list with that in the sorted list.

Look at the illustration for a better understanding:

Press + to interact
canvasAnimation-image
1 of 15

Also, here is the code:

using System;
class Program
{
    public static void SelectionSort(int[] lst)
    {
        // Traverse through all lst elements
        for (int i = 0; i < lst.Length; i++)
        {
            // Find the minimum element in unsorted lst
            int minIndex = i;
            for (int j = i + 1; j < lst.Length; j++)
            {
                if (lst[minIndex] > lst[j])
                {
                    minIndex = j;
                }
            }
            // Swap the found minimum element with the first element
            int temp = lst[i];
            lst[i] = lst[minIndex];
            lst[minIndex] = temp;
        }
    }
    public static void Main(string[] args)
    {
        int[] lst = { 8, 5, 2, 6, 9, 3, 1, 4, 0, 7 };
        SelectionSort(lst); // Calling selection sort function
        // Printing Sorted list
        Console.Write("Sorted list: [");
        Console.Write(string.Join(", ", lst));
        Console.WriteLine("]");
    }
}

Time complexity

The time complexity of this code is in O(n2)O(n^2) because finding a minimum number in the list requires iterating over the entire list for each element of the given list. The quadratic time complexity makes it impractical for large inputs.

Bubble sort

This is another famous sorting algorithm also known as sinking sort. It works by comparing adjacent pairs of elements and swapping them if they are in the wrong order. This is repeated until the list is sorted.

Think of it this way: a bubble passes over the list, catches the maximum/minimum element, and brings it over to the right side.

Press + to interact
canvasAnimation-image
1 of 31
using System;
class Program
{
    public static void BubbleSort(int[] lst)
    {
        // Traverse through all list elements
        for (int i = 0; i < lst.Length - 1; i++)
        {
            // Last i elements are already in place
            for (int j = 0; j < lst.Length - i - 1; j++)
            {
                // Traverse the list from 0 to size of lst - i - 1
                // Swap if the element found is greater than the next element
                if (lst[j] > lst[j + 1])
                {
                    int temp = lst[j];
                    lst[j] = lst[j + 1];
                    lst[j + 1] = temp;
                }
            }
        }
    }
    public static void Main(string[] args)
    {
        int[] lst = { 6, 5, 3, 1, 8, 7, 2, 4 };
        BubbleSort(lst); // Calling bubble sort function
        // Printing Sorted list
        Console.Write("Sorted list is: [");
        Console.Write(string.Join(", ", lst));
        Console.WriteLine("]");
    }
}

Time complexity

The time complexity of this code is O(n2)O(n^2). Again, this algorithm is not very efficient.

Insertion sort

Insertion sort is another famous sorting algorithm and works the way you would naturally sort in real life.

It iterates over the given list, figures out what the correct position of every element is, and inserts it there.

Press + to interact
canvasAnimation-image
1 of 17
using System;
class Program
{
    public static void InsertionSort(int[] lst)
    {
        // Traverse through 1 to len(lst)
        for (int i = 1; i < lst.Length; i++)
        {
            int key = lst[i];
            int j = i - 1;
            // Move elements of lst greater than key, to one position ahead
            while (j >= 0 && key < lst[j])
            {
                lst[j + 1] = lst[j];
                j--;
            }
            lst[j + 1] = key;
        }
    }
    public static void Main(string[] args)
    {
        int[] lst = { 6, 5, 3, 1, 8, 7, 2, 4 };
        InsertionSort(lst); // Calling insertion sort function
        // Printing Sorted list
        Console.Write("Sorted list is: [");
        Console.Write(string.Join(", ", lst));
        Console.WriteLine("]");
    }
}

Time complexity

The algorithm is O(n2)O(n^2), which, again, makes it a poor choice for large input sizes. However, notice that the complexity is actually n2n^2 only when the input list is sorted in reverse. So, the best-case complexity (when the list is sorted in the correct order) is Ω(n)\Omega(n).

Space complexity

All of the sorting algorithms discussed above are in-place, so their space complexity is O(1)O(1).