时间戳

首页 > 解决方案 > 使用快速排序在 C++ 中排序可视化器错误

c++ - 使用快速排序在 C++ 中排序可视化器错误

问题描述

因此，当我使用名为 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;
}

标签： c++sortingquicksort

解决方案

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

推荐阅读