ошибка сортировки визуализатора в c ++ с использованием быстрой сортировки

Question

поэтому, когда я создаю этот визуализатор сортировки, используя библиотеку создания игр под названием splashkit, (я знаю, что это не идеал, но это то, чему учит меня мой курс), я пытаюсь показать весь массив и показать каждый отдельный обмен.Но вместо этого он делает следующее: Видео с моей ошибкой

Я не понимаю логики моего кода, поскольку я следовал руководству для достижения этой цели.Сама сортировка в порядке и прекрасно работает, однако рисование прямоугольников странно, а не то, чего я пытаюсь достичь. Я бы хотел добиться чего-то подобного. (Без цветов / звуковых эффектов).КОД ОБНОВЛЕН:

#include "splashkit.h"

#define NUM_VALS 200

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 draw_sort(int values[], int size)
{
    clear_screen(COLOR_WHITE);
    draw_values(values, size);
    refresh_screen(60);
}

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

/* inspiration/educated from https://www.geeksforgeeks.org/quick-sort/ */
int partition (int values[], int low, int size)
{
    int pivot = values[size]; // the pivot value
    int i = (low - 1); // currently selected element

    // work out if all values have become the pivot value, loop until all have.
    for (int j = low; j <= size-1; j++)
    {
        if (values[j] <= pivot)
        {
            i++;
            swap(values[i], values[j]);
            draw_sort(values, size);
        }
    }
    swap(values[i + 1], values[size]);
    draw_sort(values, size);
    return (i+1);
}

void quick_sort (int values[], int low, int size)
{
    if (low < size)
    {
        // This is the partitioning index for quick sorting
        int pi = partition(values, low, size);

        // This sorts small partitions at a time then sorts them together.
        quick_sort(values, low, (pi - 1));
        quick_sort(values, (pi + 1), size);
    }
}

void bubble_sort(int values[], int size)
{
    for (int j = 0; j < size; j++)
    {
        for (int i = 0; i < size - 1; i++)
        {
            if (values[i] > values[i + 1])
            {
                swap(values[i], values[i + 1]);
                draw_sort(values, 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))
    {
        quick_sort(values, 0, size);
    }
}

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;
}

Answer 1

Внутри функции quick_sort size - это не размер списка, а размер текущего раздела, поэтому при вызове draw_sort вы рисуете только текущий раздел, а не весь список.Вам необходимо добавить дополнительные параметры с исходным размером списка:

int partition (int values[], int low, int partitionSize, int size)
{
    int pivot = values[partitionSize]; // the pivot value
    int i = (low - 1); // currently selected element

    // work out if all values have become the pivot value, loop until all have.
    for (int j = low; j <= partitionSize-1; j++)
    {
        if (values[j] <= pivot)
        {
            i++;
            swap(values[i], values[j]);
            draw_sort(values, size);
        }
    }
    swap(values[i + 1], values[partitionSize]);
    draw_sort(values, size);
    return (i+1);
}

void quick_sort (int values[], int low, int partitionSize, int size)
{
    if (low < partitionSize)
    {
        // This is the partitioning index for quick sorting
        int pi = partition(values, low, partitionSize, size);

        // This sorts small partitions at a time then sorts them together.
        quick_sort(values, low, (pi - 1), size);
        quick_sort(values, (pi + 1), partitionSize, size);
    }
}