QuickSortVisualizer.cpp

# include <Siv3D.hpp>    // OpenSiv3D v0.6.4

enum class State {
    None,
    Swapping,
    Pivot,
};

class QuickSortVisualizer {
public:
    QuickSortVisualizer(int32 size, double delayMS)
        : m_doWait(false)
        , m_delay(MillisecondsF(delayMS)) {
        generate(size);
    }
    ~QuickSortVisualizer() {
        m_doWait = false;
        if (m_task.isValid()) {
            m_task.wait();
        }
    }
    void generate(int32 size) {
        m_values.assign(size, 0);
        m_states.assign(size, State::None);
        for (int32 i = 1; i <= size; i++) {
            m_values[i - 1] = static_cast<int32>((Scene::Height() - 100.0) * (i / static_cast<double>(size)));
        }
    }
    void setDelayMS(double delayMS) {
        m_delay = MillisecondsF(delayMS);
    }
    void draw() const {
        double width = Scene::Width() / static_cast<double>(m_values.size());
        for (int32 i = 0; i < m_values.size(); i++) {
            Color color = Palette::White;
            if (m_states[i] == State::Swapping) {
                color = Palette::Red;
            }
            if (m_states[i] == State::Pivot) {
                color = Palette::Cyan;
            }
            RectF(Arg::bottomLeft(width * i, Scene::Height()), width, m_values[i]).draw(color);
        }
    }
    void swap(int32 i, int32 j) {
        m_states[i] = State::Swapping;
        m_states[j] = State::Swapping;
        if (m_doWait) {
            System::Sleep(m_delay);
        }
        std::swap(m_values[i], m_values[j]);
        m_states[i] = State::None;
        m_states[j] = State::None;
    }
    void shuffle() {
        m_doWait = false;
        if (m_task.isValid()) {
            m_task.wait();
        }
        m_doWait = true;
        m_task = Async([this]() { return this->shuffleImpl(); });
    }
    void sort() {
        m_doWait = false;
        if (m_task.isValid()) {
            m_task.wait();
        }
        m_doWait = true;
        m_task = Async([this]() { return this->sortImpl(0, static_cast<signed>(m_values.size()) - 1); });
    }
private:
    bool shuffleImpl() {
        for (int32 i = 0; i < m_values.size() - 1; i++) {
            int32 j = Random(i + 1, static_cast<signed>(m_values.size()) - 1);
            swap(i, j);
        }
        return true;
    }
    bool sortImpl(int32 l, int32 r) {
        if (l < r) {
            int32 pivot = partition(l, r);
            sortImpl(l, pivot - 1);
            sortImpl(pivot + 1, r);
        }
        return true;
    }
    int32 partition(int32 l, int32 r) {
        int32 pivot = m_values[r];
        m_states[r] = State::Pivot;
        int32 i = (l - 1);

        for (int32 j = l; j <= r - 1; j++) {
            if (m_values[j] <= pivot) {
                i++;
                swap(i, j);
            }
        }

        m_states[r] = State::None;
        swap(i + 1, r);

        return (i + 1);
    }
    Array<int32> m_values;
    Array<State> m_states;
    AsyncTask<bool> m_task;
    Duration m_delay;
    bool m_doWait = true;
};

void Main() {
    Window::Resize(800, 700);

    int32 size = 100;
    double delayMS = 10.0;
    QuickSortVisualizer sortvis(size, delayMS);

    while (System::Update()) {
        if (SimpleGUI::Button(U"Generate", { 10, 10 })) {
            sortvis.generate(size);
        }
        if (SimpleGUI::Button(U"Shuffle", { 140, 10 })) {
            sortvis.shuffle();
        }
        if (SimpleGUI::Button(U"Sort", { 250, 10 })) {
            sortvis.sort();
        }
        double innerSize = size;
        SimpleGUI::Slider(U"Size : {:.0f}"_fmt(innerSize), innerSize, 10.0, 1000.0, Vec2{ 10, 50 }, 100, 320);
        SimpleGUI::Slider(U"Delay : {:.0f}ms"_fmt(delayMS), delayMS, 1.0, 100.0, Vec2{ 440, 50 }, 120, 230);
        size = static_cast<int32>(innerSize);
        sortvis.setDelayMS(delayMS);

        sortvis.draw();
    }
}