-1

Задача такая, реализовать алгоритм сортировки слияния, прочитав варианты реализации на других сайтах и версию вики, реализация показалась мне довольно громоздкой и не совсем элегантной, в собственной версии поставил себе задачу:
- Выполнить рекурсивно.
- Одной функцией.
- Уменьшить число операнд.
- Свести количество параметров до передаваемого в функцию указателя на массив и размера самого массива.
После некоторых преобразований свел код, до ниже представленного, компилируется с ошибкой "stuck overflow: обращение к запрещенному участку памяти", или "нарушение прав доступа при чтении по адресу..".
Долгое время не могу найти утечку и прошу кого-либо более внимательного заметить и сказать мне, где именно происходит выход за пределы массива в данном коде:

void merge_sort(int* unsorted, unsigned int size)
{
    if (size < 2) return;

    unsigned int middle = size >> 1;

    merge_sort(unsorted, middle);
    merge_sort(unsorted + middle, size - middle);

    int* first = unsorted;
    int* second = unsorted + middle;

    int* sorted = new int[size];

    while (first != (unsorted + middle) && second != (unsorted + size))
        *sorted++ = *first < *second ? *first++ : *second++;

    while (first != (unsorted + middle))
        *sorted++ = *first++;
    while (second != (unsorted + size))
        *sorted++ = *second++;

    sorted -= size;
    while (unsorted != second)
        *unsorted++ = *sorted++;

    delete[] sorted;
}
  • На данный момент: путем вывода значений в лог, обнаружил, функция работает корректно до последнего цикла, который по непонятным причинам становится бесконечным..
  • Полностью рабочая версия. Спустя всего-то..
5
  • 1
    Почему size >> 1, а не нормальное человеческое size / 2? Откуда тут взялся сдвиг? 2 янв 2018 в 22:56
  • size >> 1 <=> size / 2^1, что по сути быстрее и отсутствует неявное преобразование типов double to int в случае size / 2 2 янв 2018 в 23:16
  • Во-первых, это нисколько не "быстрее", ибо для unsigned int эти варианты абсолютно строго эквивалентны. Никогда в C/С++ коде нет смысла вручную "оптимизировать" целочисленное деление или умножение на константу времени компиляции. А уж "оптимизировать" деление на 2 - это грубейшая профанация. Во-вторых, какой еще "double to int"??? Где вы тут увидели double??? 2 янв 2018 в 23:33
  • В вашем коде наблюдаются какие-то дикие попытки экономить на переменных. Не надо этого делать. Заведите в два раза больше переменных со своими четкими ролями, и код станет намного удобочитаемее. 4 янв 2018 в 19:29
  • @AnT, спасибо за совет, но так будет нечестно 4 янв 2018 в 23:45

1 ответ 1

3
  • (Уже исправлено.) Ошибка в условии первого цикла

    while (first != (unsorted + middle) || second != (unsorted + size))
        *sorted++ = *first < *second ? *first++ : *second++;
    

    приведет к вылету за пределы массива из-за || в условии. Тут, очевидно, нужно &&, а не ||.

  • (Уже исправлено.) Очевидная ошибка при обработке "хвоста" массива

    while (second != (unsorted + middle))
        *sorted++ = *second++;
    

    У вас second должен идти до unsorted + size, а не до unsorted + middle, как вы сами прекрасно знаете, судя по условию первого цикла.

  • (Уже исправлено.) Далее написана вообще какая-то полнейшая бессмыслица

    while (sorted != (sorted - size))
        *(unsorted-- + size) = *sorted--;
    

    Условие этого цикла всегда истинно, если size не равно 0. То есть это бесконечный цикл. Что вы хотели этим сказать?

  • (Уже исправлено.) Ваш "замысел" с последним циклом понятен (хоть и реализован криво), однако, кроме бессмысленного условия, страдает и от других косяков. А именно:

    • После предыдущих циклов указатель sorted указывает на "мусорное" значение после последнего записанного. В последнем цикле ваше копирование из *sorted-- будет на первом шаге копировать это "мусорное" значение. Так как ваш цикл задуман как делающий ровно нужное количество итераций - size - то ясно, что он где-то "потеряет" какое-то нужное значение.
    • К указателю unsorted применяется --. Кто вам разрешил это делать? Указатель unsorted может указывать на начало некоего массива. Адресная арифметика в С++ не разрешает "выгонять" указатель влево за начало массива.
13
  • программа вылетает на именно первом цикле, со сравнением, простите за сырой код, там механическая ошибка копипасты в первом случае, где вы указали, а "нелепица" имеет по моему такой смысл: после предыдущей инкрементации в цикле, указатель sorted указывает на последний элемент подмассива, поэтому я присваиваю в обратном порядке, чтобы не переприсваивать ему лишний раз адресс первого элемента. 2 янв 2018 в 23:09
  • добавлю, что копирование второго хвоста излишнее, а последний while(), очевидно крайне кривое копирование элементов в исходный массив.
    – Fat-Zer
    2 янв 2018 в 23:09
  • @PostPunkTheSmith, (sorted - size) вычисляется на каждой итерации цикла заново.
    – Fat-Zer
    2 янв 2018 в 23:13
  • 1
    @PostPunkTheSmith: Подразумевая, что необходимо исправить ошибки о которых пишет AnT, всё так и есть: выполняется только один из этих двух циклов. И это будет работать. Но от второго цикла можно избавится, сократив тем самым издержки на копирование в sorted и обратно.
    – Fat-Zer
    3 янв 2018 в 0:24
  • 1
    @Fat-Zer: Логично. Два цикла, следующие за главным циклом, должны копировать данные прямо в массив unsorted. Копировать их сначала в sorted, а потом оттуда в unsorted - это бессмысленное переливание туда-сюда. Но это уже оптимизация. Сначала можно было бы заставить заработать существующий вариант. 3 янв 2018 в 0:27

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.