sorts.cpp

/**
 * Sweet merge-sort action: https://youtu.be/3WWtrx30mTk
 */
#include "splashkit.h"

#define NUM_VALS 40

void draw_values(const int values[], int size) 
{
    int x = 0;
    int y;
    int rect_height;
    int rect_width = screen_width() / size;

    for (int i = 0; i < size; i++)
    {
        rect_height = values[i];
        y = screen_height() - rect_height;

        fill_rectangle(COLOR_RED, x, y, rect_width, rect_height);
        draw_rectangle(COLOR_WHITE, x, y, rect_width, rect_height);
        
        x += rect_width;
    }
}

void swap(int &value1, int &value2)
{
    int temp = value1;
    value1 = value2;
    value2 = temp;
}

void draw_sort(int values[], int size)
{
    clear_screen(COLOR_WHITE);
    draw_values(values, size);
    refresh_screen(60);
}

void bubble_sort(int values[], int size)
{
    for (int i = 0; i < size; i++)
    {
        for (int j = 0; j < size - 1; j++)
        {
            if (values[j] > values[j + 1])
            {
                swap(values[j], values[j + 1]);
                draw_sort(values, NUM_VALS);
            }
        }
    }
}

/**
 * Merge the elements from two consecutive sorted (sub)lists from the left,
 * into a single sorted (sub)list, in place.
 * 
 * @param values            The original entire list being sorted in place
 * @param start_idx         The start idx for the left sublist
 * @param right_start_idx   The start idx for the right sublist
 * @param size              The size of both sublists
 */
void merge_left(int values[], int start_idx, int right_start_idx, int size)
{
    // use a temporary array to contain the results of the merge
    int result[size];
    int result_i = 0;

    // keep track of where we are up to in each sublist
    int left_i = start_idx;
    int right_i = right_start_idx;

    // until we hit the end of one of the sublists
    while (left_i < right_start_idx && right_i < start_idx + size)
    {
        // store the smallest value at the front of either list and 
        // increment that list's index
        if (values[left_i] <= values[right_i])
        {
            result[result_i] = values[left_i];
            left_i++;
        }
        else
        {
            result[result_i] = values[right_i];
            right_i++;
        }
        // increment the result list index
        result_i++;
    }
    // if we hit the end of the right sublist, push the rest of the left sublist
    while (left_i < right_start_idx)
    {
        result[result_i] = values[left_i];
        left_i++;
        result_i++;
    }
    // or if we hit the end of the left sublist, push the rest of the right
    while (right_i < start_idx + size)
    {
        result[result_i] = values[right_i];
        right_i++;
        result_i++;
    }

    // paste the merged results back over both sublists
    for (int j = 0; j < result_i; j++)
    {
        values[start_idx + j] = result[j];
        // it's slightly imperfect to have draw_sort occur here, but it's more fair
        // since the draw occurs the same number of times as for bubble sort
        draw_sort(values, NUM_VALS);
    }
}

/**
 * A radical in-place merge sort implementation.
 * 
 * The functional version is much simpler, but hey, this was fun.
 * 
 * @param values    The original entire list being sorted in place
 * @param size      The size of the current sublist being sorted
 * @param start_idx The start idx of the current sublist being sorted
 */
void merge_sort(int values[], int size, int start_idx)
{
    // since we're doing an in-place sort, doing nothing for size == 0 is the
    // base case to end recursion
    if (size > 1)
    {
        // split the current sublist into right and left parts, store their sizes
        // and the start index of the rightmost sublist
        int left_sublist_size, right_sublist_idx, right_sublist_size;
        left_sublist_size = size / 2;
        right_sublist_idx = start_idx + left_sublist_size;
        right_sublist_size = size - left_sublist_size;

        // merge_sort the left half of the list
        merge_sort(values, left_sublist_size, start_idx);
        // merge_sort the right half of the list
        merge_sort(values, right_sublist_size, right_sublist_idx);

        // merge the two sorted lists from the left
        merge_left(values, start_idx, right_sublist_idx, size);
    }
}

void random_fill_array(int values[], int size)
{
    for (int i = 0; i < size; i++) 
    {
        values[i] = rnd(screen_height()) + 1;
    }
}

void handle_input(int values[], int size)
{
    if (key_typed(R_KEY))
    {
        random_fill_array(values, size);
    }
    else if (key_typed(S_KEY))
    {
        bubble_sort(values, size);
    }
    else if (key_typed(D_KEY))
    {
        merge_sort(values, size, 0);
    }
}

int main()
{
    int values[NUM_VALS];

    open_window("Sort Visualiser", 800, 600);
    
    random_fill_array(values, NUM_VALS);

    while ( not quit_requested() )
    {
        process_events();
        handle_input(values, NUM_VALS);
        
        draw_sort(values, NUM_VALS);
    }

    return 0;
}