‎

1. Sorting algorithm efficiency
2. Bubble Sort
3. Selection sort
4. Insertion Sort

Video - Bubble Sort:

Video - Insertion Sort:

Video - Selection Sort:

There are various sorting algorithms that are used to put data in ascending or descending order. Some algorithms are slow and some are fast, though the faster ones tend to have more complex code and the slower ones have simpler code. We will be covering the slow, simple algorithms here.

While sorting, we look at two different items in the array and swap them if they're out of order. How we traverse the array is what makes the different algorithms.

You don't need to memorize these algorithms and I don't test on them. You will see them in future Computer Science courses, but these algorithms aren't secret, you can find pseudocode and implementations everywhere online. The main idea is to see how they work and become acquainted with them.

In the real world you won't be implementing sorting algorithms; you'll be using sorts that are already provided by the language or some third-party library.

1. Sorting algorithm efficiency

Sorting algorithm efficiency (From https://www.bigocheatsheet.com/)

Algorithm	Best time	Average time	Worst time
Bubble Sort	Ω(n)	Θ(n²)	O(n²)
Insertion Sort	Ω(n)	Θ(n²)	O(n²)
Selection Sort	Ω(n²)	Θ(n²)	O(n²)
Merge Sort	Ω(n log(n))	Θ(n log(n))	O(n log(n))
Quick Sort	Ω(n log(n))	Θ(n log(n))	O(n²)

2. Bubble Sort

Video: Bubble Sort Visualization by Abhilas Biswas

vector<string> BubbleSort(vector<string> arr)
{
    for ( size_t i = 0; i < arr.size() - 1; i++ )
    {
        for ( size_t j = 0; j < arr.size() - i - 1; j++ )
        {
            if ( arr[j] > arr[j+1] )
            {
                Swap( arr[j], arr[j+1] );
            }
        }
    }
    return arr; // Return the sorted version of the vector
}

With Bubble sort the outer loop makes sure we go from the beginning to the end of the array (minus one). The inner loop, with variable j, is the one that is actually used to check each element j with its right neighbor j+1. If arr[j] is greater than arr[j+1] then they're out of order and will be swapped.

3. Selection sort

Video: Selection Sort Visualization by Abhilas Biswas

vector<string> SelectionSort(vector<string> arr)
{
    for ( size_t i = 0; i < arr.size() - 1; i++)
    {
        size_t minIndex = i;
        for ( size_t j = i + 1; j < arr.size(); j++ )
        {
            if ( arr[j] < arr[minIndex] )
            {
                minIndex = j;
            }
        }
        if ( minIndex != i )
        {
            Swap( arr[i], arr[minIndex] );
        }
    }
    return arr; // Return the sorted version of the vector
}

With Selection Sort our outer loop i goes from the beginning to the end (minus one). At the start of this outer loop, we assume the smallest item we've found is that first item at position i. We keep a variable minIndex to keep track of the smallest value we find.

The internal loop j starts at i's right neighbor and goes to the end of the array. Each arr[j] will be inspected and if arr[j] is less than the arr[minIndex], then the minIndex is now set to j.

After the j loop ends, if the minIndex is not equal to i, then that means we found a new smallest item, so we swap arr[i] and arr[minIndex].

4. Insertion Sort

Video: Insertion Sort Visualization by Professor Painter

vector<string> InsertionSort(vector<string> arr)
{
    size_t i = 1;

    while ( i < arr.size() )
    {
        size_t j = i;
        while ( j > 0 && arr[j-1] > arr[j] )
        {
            Swap( arr[j], arr[j-1] );
            j--;
        }

        i++;
    }

    return arr; // Return the sorted version of the vector
}

With Insertion Sort, our outer loop goes from i=1 to the end of the array. We initialize j to i's value, then our internal loop moves backwards from j's current position while the item on the left (arr[j-1]) is greater than the current value (arr[j]). While it finds things out of order, it swaps the two (arr[j] and arr[j-1]) and then moves j to the left.

Table of Contents

1. Sorting algorithm efficiency

2. Bubble Sort

3. Selection sort

4. Insertion Sort