Skip to main content

Sorting algorithms

Computers spend a lot of time sorting while processing data. Once sorting is done, many other problems becomes very easy. It is also one of the most studied problem in computer science. Many of the interesting ideas such as dive-and-conquer, randomized algorithms, lower bounds etc. can be found in the context of sorting. Here we will look into some of the sorting algorithms and how they scales with increasing problem size.

Permutation sort​

Given an array, we create all possible permutations of the array items, then check if the one of those permutations are sorted. This algorithm is extremely inefficient, there are n!n! possible permutations of nn items. Even for a relatively small number of input size 20, (20)!≈2×1018(20)! \approx 2 \times 10^{18}. For each step, we also need about O(n)\mathcal{O}(n) checks to find out if one of the permutations is sorted.

Selection sort​

Here is how the selection sort works: say we are given the following array to sort: [5, 8, 2, 3, 7, 9]

Step 1: find the biggest element in first (n - 1) element and swap it with the last element if it is bigger than the last element else do nothing

Step 2: find biggest element in first (n - 2) element, and swap it with (n-1)th element if it is bigger

Below is an implementation in C++.

src/cpp/misc/selection_sort.cpp
#include <iostream>
#include <tuple>
using namespace std;

tuple<int, int> find_biggest(int arr[], int size)
{
    int biggest = arr[0];
    int id = 0;

    for (int i = 0; i < size; i++)
    {
        if (arr[i] > biggest)
        {
            biggest = arr[i];
            id = i;
        }
    }

    return make_tuple(biggest, id);
}

int main()
{
    int arr[] = {5, 8, 2, 3, 7, 4};
    const int SIZE = 6;

    for (int i = 1; i < SIZE; i++)
    {
        int biggest, id;
        tie(biggest, id) = find_biggest(arr, SIZE - i);

        if (biggest > arr[SIZE - i])
        {
            int tmp = arr[SIZE - i];
            arr[SIZE - i] = biggest;
            arr[id] = tmp;
        }
    }

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i] << "  ";
    }
    cout << endl;

    return 0;
}

Insertion sort​

src/cpp/misc/insertion_sort.cpp
#include <iostream>
using namespace std;

int main()
{
    int arr[] = {5, 8, 2, 3, 7, 4};
    const int SIZE = 6;

    for (int i = 1; i < SIZE; i++)
    {
        int j = i;
        while (j > 0 && arr[j] < arr[j - 1])
        {
            int tmp = arr[j];
            arr[j] = arr[j - 1];
            arr[j - 1] = tmp;
            j--;
        }
    }

    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i];

        if (i != SIZE - 1)
        {
            cout << ", ";
        }
    }
    cout << endl;

    return 0;
}

Both selection sort and insertion sort has time complexity O(n2)\mathcal{O}(n^2).

Merge sort​

src/cpp/misc/merge_sort.cpp
#include <iostream>
using namespace std;

void print_array(int arr[], const int SIZE)
{
    for (int i = 0; i < SIZE; i++)
    {
        cout << arr[i];
        if (i < SIZE - 1)
        {
            cout << ", ";
        }
    }
    cout << endl;
}

void merge(int arr[], const int start, const int center, const int end)
{
    // temporary arrays
    auto *left_array = new int[center - start];
    auto *right_array = new int[end - center];

    // copy data to temp arrays
    for (auto i = 0; i < center - start; i++)
    {
        left_array[i] = arr[start + i];
    }

    for (auto i = 0; i < end - center; i++)
    {
        right_array[i] = arr[center + i];
    }

    // merge
    int i = 0;
    int j = 0;
    int left = start;
    while (left < end)
    {
        if ((j >= end - center) || ((i < center - start) && (left_array[i] < right_array[j])))
        {
            arr[left] = left_array[i];
            i++;
        }
        else
        {
            arr[left] = right_array[j];
            j++;
        }
        left++;
    }

    delete[] left_array;
    delete[] right_array;
}

void merge_sort(int arr[], int start, int end)
{
    if (end - start > 1)
    {
        auto center = (start + end + 1) / 2;
        merge_sort(arr, start, center);
        merge_sort(arr, center, end);
        merge(arr, start, center, end);
    }
}

int main()
{
    int arr[] = {5, 8, 2, 3, 7, 4};
    const int SIZE = 6;

    merge_sort(arr, 0, SIZE);
    print_array(arr, 6);

    return 0;
}

Merge sort has time complexity O(nlog⁡n)\mathcal{O}(n \log n). Note that for any comparison model, there are n!n! possible outcomes for a problem size nn. Minimum height of such as descision tree would be log⁡(n!)≈nlog⁡n\log(n!) \approx n \log n. Therefore, merge sort is best possible (or close to best possible) solution for any sorting algorithm based on comparison model. Can we do better?

Linear sort​

It takes constant amount of time to access a memory location (RAM) by its address. If we are able to build a direct access array (DAA), we can get its elements by its index. We can build key value pairs, where keys are index of an DAA. If we have to search through the array, we can get an item in constant time. Say we have nn items and the key space is uu. If nn and uu are of the same order, then such an algorithm would be efficient. Example: say we have student IDs (keys) based on their ranking.

What if key space is of the order of n2n^2? In that case, we can break down each key in a tuple of (a, b), where a = u / n (integer division), and b = u % n (remainder of modulo division). Example: say we have a list of 5 numbers: 24, we can transform them into 4. Now, if we need to sort them (we can call tuple sort), we need to sort first based on the least significant tuple digit (here second digit), and we obtain: 4. Finally, we sort by the most significant tuple digit: 4.

info

Note that we need a stable sorting algorithm to sort above tuple, i.e., it maintains the order of numbers in the original input list. If the input tuple was 1 after sorting based on most significant tuple digit (i.e., first digit), it should return 1.

Resources​