Вставка сортировки действует странно C ++ - PullRequest
Новая
       36

Вставка сортировки действует странно C ++

0 голосов
/ 13 ноября 2018

Я хочу создать функцию для сортировки случайных чисел (сгенерированных с помощью другой функции), и я пытался сделать это некоторое время, но ничего не получалось.Теперь у меня проблема в том, что иногда моя программа компилируется без каких-либо проблем, а иногда она говорит «векторный индекс вне диапазона», и даже если она компилируется правильно, она вставляет некоторые числа в неправильном порядке (особенно, когда следующее число для сортировки меньше, чемПредыдущая).Я пытался использовать отладчик и выяснить, что не так, но для меня все выглядит хорошо.Не могли бы вы быть так добры и помочь мне?Большое спасибо. 

std::vector <int> insertion_sort(std::vector <int> generated)
{
    using namespace std;
    bool emplaced = false;
    vector <int> buffor(1);

    buffor[0] = generated[0];

    for (int i = 1; i < generated.size(); i++)
    {
        emplaced = false;

        if (generated[i] >= buffor[i-1])
        {
            buffor.push_back(generated[i]);
        }
        else
        {
            int x = 2;
            while (((i - x) > -1))
            {
                if (emplaced == true)
                {
                    break;
                }

                if ((i - x) == 0)
                {
                    buffor.emplace(buffor.begin(), generated[i]);
                    emplaced = true;
                }

                if (generated[i] < bufor[i - x])
                {

                }
                else
                {
                    buffor.emplace(buffor.begin() + (i-x), generated[i]);
                    emplaced == true;
                }

                x++;
            }
        }

    }

    return buffor;
}

1 Ответ

0 голосов
/ 13 ноября 2018

Вставка сортировки является простым алгоритмом сортировки и может быть реализована более компактным и простой код, подобный следующему:

ДЕМО здесь. 

std::vector<int> insertion_sort(const std::vector<int>& generated)
{
    auto shifted(generated);

    for (std::size_t j = 1; j < shifted.size(); ++j) 
    {
        const auto temp = shifted[j];

        if(shifted[j-1] > temp)
        {
            int i = j;

            do{
                shifted[i] = shifted[i-1];
                --i;
            } while(i > 0 && shifted[i-1] > temp);

            shifted[i]=temp;
        }
    }

    return shifted;    
}
...