Вставить элемент в отсортированный массив

Question

У меня есть сортировка, что мне нужно вставить элементы и сохранить их в подпоследовательности binary-search es вызовов. Какой алгоритм я должен использовать? или, может быть, это преждевременная optmization, и я должен просто вставить элемент и вызвать shell-sort (который я буду применять в качестве замены для текущего)?

Если эта информация полезна: количество элементов может быть большим. Это действительно переменная, может содержать от 1 до 10 или даже от 1 до 1000+ элементов. Если вам интересно, почему это слишком много переменных, я пишу синтаксический анализ.

Answer 1

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

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

Пример:

int *array[] = malloc(3*sizeof(int)); 
array[0] = 0; 
array[1] = 2; 
array[2] = 3; 

// To insert 1 for example you will have to do... 
int *new_array[] = malloc(4*sizeof(int)); // Just for the example I make a tight fit, on the code you should allocate it a bit bigger if you expect more inserts to avoid unnecessary mallocs and frees 

memmove(new_array,array,sizeof(int)); // Moving the 0 
new_array[1] = 1; // Inserting the new element 
memmove(new_array[2],array[1],2*sizeof(int)); // Moving the 2 and 3 

free(array); // Get rid of the old array 
array = new_array; 
new_array = NULL;