Алгоритм Сортировки Слиянием на C++

215
04 января 2018, 23:46

Задача такая, реализовать алгоритм сортировки слияния, прочитав варианты реализации на других сайтах и версию вики, реализация показалась мне довольно громоздкой и не совсем элегантной, в собственной версии поставил себе задачу:
- Выполнить рекурсивно.
- Одной функцией.
- Уменьшить число операнд.
- Свести количество параметров до передаваемого в функцию указателя на массив и размера самого массива.
После некоторых преобразований свел код, до ниже представленного, компилируется с ошибкой "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;
}
  • На данный момент: путем вывода значений в лог, обнаружил, функция работает корректно до последнего цикла, который по непонятным причинам становится бесконечным..
  • Полностью рабочая версия. Спустя всего-то..
Answer 1
  • (Уже исправлено.) Ошибка в условии первого цикла

    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 может указывать на начало некоего массива. Адресная арифметика в С++ не разрешает "выгонять" указатель влево за начало массива.
READ ALSO
Socket чтение buffer

Socket чтение buffer

Здравствуйте! Я в c++ новичок и у меня возникла проблема, не знаю как прочитать ответ из буфера socket сервера

163
Перегруженные конструкторы?

Перегруженные конструкторы?

В заголовочном файле:

186
Задача для прокачки мозгов (IQ) [требует правки]

Задача для прокачки мозгов (IQ) [требует правки]

Имеется массив с положительными элементами (N элементов)Районном называется отрезок (l, r) (использовать нужно K районов, ни меньше ни больше),...

224