Лучший алгоритм сдвига массива?

Если вы после минимальных изменений в вашем подходе, вы можете использовать memmove() функция, которая потенциально быстрее, чем ваша собственная версия вручную. Вы не можете использовать memcpy() по совету одного комментатора, поскольку области памяти не могут перекрываться (поведение не определено, если они это делают).

Существует не так много, что вы можете сделать без изменения типа вашего хранилища или вашего алгоритма. Однако, если вы перейдете к использованию связанного списка, операция станет значительно более эффективной, хотя вы будете делать больше выделения памяти. Если распределение действительно является проблемой (и если вы не находитесь на ограниченной встроенной системе, вероятно, нет), то распределители пула или аналогичные подходы могут помочь.

РЕДАКТИРОВАТЬ: Перечитывая ваш вопрос, я предполагаю, что вы на самом деле не используете Heapsort, вы просто имеете в виду, что ваш массив был размещен в куче (т.е. используя malloc()) а ты делаешь простой сортировка вставок. В этом случае информация, представленная ниже, не очень полезна для вас напрямую, хотя вы должны знать, что сортировка вставкой является довольно неэффективной по сравнению с массовой вставкой, за которой следует лучший алгоритм сортировки (например, Quicksort который вы можете реализовать с помощью стандартной библиотеки qsort() функция). Если вам нужен только самый низкий (или самый высокий) элемент вместо полностью отсортированного порядка, то Heapsort по-прежнему полезен для чтения.

Если вы используете стандарт Пирамидальная сортировка тогда вам вообще не понадобится эта операция — элементы добавляются в конец массива, а затем операция «heapify» используется, чтобы поменять их на правильную позицию в куче. Для каждого обмена требуется только одна временная переменная, чтобы поменять местами два элемента — для этого не нужно ничего перемешивать, как в вашем фрагменте кода. Требуется, чтобы все в массиве было одинакового размера (либо строка с фиксированным размером на месте, либо, что более вероятно, указатель), но ваш код, похоже, уже в любом случае предполагает это (и использует строки переменной длины в стандартном char массив был бы довольно странной вещью).

Обратите внимание, что строго говоря, Heapsort работает на двоичном дереве. Так как вы имеете дело с массивом, я предполагаю, что вы используете реализацию, в которой используется непрерывный массив, где дочерние узлы индекса n хранятся в документах 2n а также 2n+1 соответственно. Если это не так или вы вообще не используете Heapsort, вам следует более подробно объяснить, что вы пытаетесь сделать, чтобы получить более полезный ответ.

РЕДАКТИРОВАТЬ: Ниже приведен ответ на обновленный код выше.

Основная причина, по которой вы видите проблему во время освобождения, заключается в том, что вы растоптали какую-то память — иными словами, вы копируете что-то, выходящее за рамки выделенной области. Это действительно плохая вещь, поскольку вы перезаписываете значения, которые система использует для отслеживания ваших распределений, и вызывают всевозможные проблемы, которые обычно приводят к сбою вашей программы.

Похоже, у вас есть небольшая путаница относительно природы выделения и освобождения памяти, прежде всего. Вы выделяете массив char*, что само по себе хорошо. Затем вы выделяете массивы char для каждой строки, что тоже хорошо. Тем не менее, вы тогда просто позвоните free() для начального массива — этого недостаточно. Там должен быть призыв к free() соответствовать каждому вызову malloc()так что вам нужно освободить каждую строку, которую вы выделяете а потом освободить начальный массив.

Во-вторых, вы установили sizeToMove к кратному sizeof(MAX_STRING_SIZE)что почти наверняка не то, что вы хотите. Это размер переменной, используемой для хранения MAX_STRING_SIZE постоянная. Вместо этого вы хотите sizeof(char*), На некоторых платформах они могут быть одинаковыми, и в этом случае все будет работать, но это не гарантируется. Например, я ожидаю, что он будет работать на 32-битной платформе (где int а также char* одинакового размера), но не на 64-битной платформе (где их нет).

В-третьих, вы не можете просто назначить строковую константу (например, "hello world") к выделенному блоку — что вы делаете здесь замена указатель Вам нужно использовать что-то вроде strncpy() или же memcpy() скопировать строку в выделенный блок. Я предлагаю snprintf() для удобства, потому что strncpy() проблема в том, что он не гарантирует прекращение результата, но решать вам.

В-четвертых, вы все еще используете memcpy() и не memmove() перетасовывать предметы вокруг.

Наконец, я только что увидел ваш комментарий, который вы должны использовать new а также delete, Там нет эквивалента realloc() для них, но это нормально, если все известно заранее. Похоже, что вы пытаетесь сделать что-то вроде этого:

bool addItem(const char *item, char *list[], size_t listSize, size_t listMaxSize)
{
// Check if list is full.
if (listSize >= listMaxSize) {
return false;
}
// Insert item inside list.
for (unsigned int i = 0; i < listSize; ++i) {
if (strcmp(list[i], item) > 0) {
memmove(list + i + 1, list + i, sizeof(char*) * (listSize - i));
list[i] = item;
return true;
}
}
// Append item to list.
list[listSize] = item;
return true;
}

Я не скомпилировал и не проверил это, так что следите за ошибками и тому подобное, но, надеюсь, вы поняли идею. Эта функция должна работать независимо от того, используете ли вы malloc() а также free() или же new а также delete, но предполагается, что вы уже скопировали строку item в выделенный буфер, который вы будете хранить вокруг, потому что, конечно, он просто хранит указатель.

Помните, что, конечно, вам нужно обновить listSize Вы сами вне этой функции — она ​​просто вставляет элемент в нужную для вас точку в массиве. Если функция возвращает true затем увеличьте свою копию listSize на 1 — если вернется false тогда вы не выделили достаточно памяти, чтобы ваш элемент не был добавлен.

Также обратите внимание, что в C и C ++, для массива list синтаксис &list[i] а также list + i полностью эквивалентны — используйте первый вместо memmove() позвоните, если вам будет легче разобраться.