Задача такая, реализовать алгоритм сортировки слияния, прочитав варианты реализации на других сайтах и версию вики, реализация показалась мне довольно громоздкой и не совсем элегантной, в собственной версии поставил себе задачу:
- Выполнить рекурсивно.
- Одной функцией.
- Уменьшить число операнд.
- Свести количество параметров до передаваемого в функцию указателя на массив и размера самого массива.
После некоторых преобразований свел код, до ниже представленного, компилируется с ошибкой "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;
}
(Уже исправлено.) Ошибка в условии первого цикла
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
может указывать на начало некоего массива. Адресная арифметика в С++ не разрешает "выгонять" указатель влево за начало массива.Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Перевод документов на английский язык: Важность и ключевые аспекты
Здравствуйте! Я в c++ новичок и у меня возникла проблема, не знаю как прочитать ответ из буфера socket сервера
Имеется массив с положительными элементами (N элементов)Районном называется отрезок (l, r) (использовать нужно K районов, ни меньше ни больше),...