使用quicksort在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);
    }
}