Сортированная приоритетная очередь массива

Question

Я реализую отсортированную очередь приоритетов массива и сортирую при вставке.По какой-то причине очередь не выходит полностью отсортированной.До сих пор правильно ли я это внедряю и как мне это исправить?

void insertInt(int numToIns)
{
    if (total == 0)
    {
        q[0] = numToIns;
        minimum = numToIns;
    }
    else if (total != 0)
    {
        if (numToIns <= minimum)
        {
            minimum = numToIns;
            for (int move = total; move >= 0; --move)
            {
                q[move + 1] = q[move];
            }
            q[0] = numToIns;
        }
        else if (numToIns < q[total])
        {
            bool numFound = false;
            for (int j = 0; numFound != true; ++j)
            {
                if (numToIns <= q[j])
                {
                    numFound = true;
                    for (int move = total; move >= j; --move)
                    {
                        q[move + 1] = q[move];
                    }
                    q[j] = numToIns;
                }
            }

        }
        else if (numToIns >= q[total - 1])
        {
            q[total] = numToIns;
        }
    }
    ++total;
}

Answer 1

Не уверен, как выглядит ваш текущий код, но он должен это делать:

#include <ctime>
#include <cstdlib>
#include <cstdio>
#include <iostream>

std::size_t total;
int q[100];
int minimum;

void print()
{
    for (std::size_t i{}; i < total; ++i)
        std::cout << q[i] << ' ';
    std::cout.put('\n');
}

void insertInt(int numToIns)
{
    if (total == 0)
    {
        q[0] = numToIns;
        minimum = numToIns;
    }
    else if (total != 0)
    {
        if (numToIns <= minimum)
        {
            minimum = numToIns;
            for (std::size_t move{ total }; move >= 0; --move)
            {
                q[move + 1] = q[move];
            }
            q[0] = numToIns;
        }
        else if (numToIns < q[total - 1])
        {
            bool numFound = false;
            for (std::size_t j{}; !numFound; ++j)
            {
                if (numToIns <= q[j])
                {
                    numFound = true;
                    for (std::size_t move{ total - 1 }; move >= j; --move)
                    {
                        q[move + 1] = q[move];
                    }
                    q[j] = numToIns;
                }
            }

        }
        else if (numToIns >= q[total - 1])
        {
            q[total] = numToIns;
        }
    }
    ++total;
}

int main()
{
    std::srand(static_cast<unsigned>(std::time(nullptr)));

    for (int i{}; i < 20; ++i) {
        insertInt(std::rand() % 20 + 1);
        print();
    }
}

Обратите внимание, что три котенка умерли из-за того, что я написал этот код: (

Нет версии bs:

void insertInt(int num)
{
    std::size_t pos{};
    while (pos < total && num > q[pos])
        ++pos;

    for (std::size_t k{ total }; k > pos; --k)
        q[k] = q[k - 1];

    q[pos] = num;
    ++total;
}

Чтобы не проходить через массив, если число для вставки больше, чем последний элемент, можно добавить один особый случай:

void insertInt(int num)
{
    if (num > q[total - 1]) {
        q[total++] = num;
        return;
    }

    std::size_t pos{};
    while (pos < total && num > q[pos])
        ++pos;

    for (std::size_t k{ total }; k > pos; --k)
        q[k] = q[k - 1];

    q[pos] = num;
    ++total;
}