копия против ручного копирования массива в C++

Question

Мне нужно отсортировать массив тысяч записей. Я помещаю каждую новую запись в нужное место, поэтому мне нужно изменить индекс остальных записей в моем массиве. Я делаю в Мануалах как:

db[j]=record; 
    cout<<tmp.oName<<endl; 
    while (j++!=size-1){ 
     tmp2=db[j]; 
     db[j]=tmp; 
     tmp=db[j]; 
    } 

И вот идет мой вопрос: было бы значительно быстрее создать новый массив и использовать копию, или не было бы заметно вычислительное времени и улучшение использования памяти у моего текущего кода? Я довольно новичок в C++, поэтому я не уверен, как эта функция работает внутри.

Включает, я могу использовать:

#include <iostream> 
#include <iomanip> 
#include <string> 
#include <cstring> 
#include <cstdlib> 
#include <cstdio> 

Answer 1

Если вы сделаете копию массива, затем скопируйте его, он будет медленнее и будет использовать больше памяти.

Скажите, что у вас есть массив с N пятнами, а я - индекс, в котором находится ваш новый предмет. Копирование массива означает, что вы используете N больше памяти и копируете элементы N раз. Если вы просто сдвигаете записи, вы не используете больше памяти и выполняете операции N-I, так как вам нужно только перемещать элементы после нового.

Answer 2

Это лучше, чтобы проверить структуры данных STL в вашем case.Try кучного сортировать или быстрой сортировки, если вы не можете использовать STL.

Answer 3

Нет, не было бы быстрого создания нового массива. Однако было бы не использовать пузырьковый вид. Вместо этого используйте что-то вроде быстрой сортировки. Просто google quick sort C++, чтобы увидеть сотню примеров этого.

Answer 4

Если вам не разрешено использовать контейнеры и алгоритмы STL, вы все равно можете поместить записи в вектор, а затем закодировать свой собственный сортир быстрой сортировки или слияния, который является несгибаемым. Быстрая сортировка более эффективна, чем сортировка или сортировка пузырьков.

FYI:

http://www.algolist.net/Algorithms/Sorting/Quicksort

Answer 5

Похоже, вы пытаетесь создать свой собственный отсортированный список.

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

EDIT:

Это одна из затрат на использование списка на основе массива (в отличие от связанного списка) - вставка занимает линейное время O (N)

Answer 6

Если вам это нужно для реальной жизни , используйте STL qsort (http://www.cplusplus.com/reference/cstdlib/qsort/). Если вам это нужно для домашней работы, создание нового массива будет дорогостоящим из-за времени запуска malloc.

Answer 7

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

Answer 8

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

С другой стороны, способ, которым вы описываете вставку, сродни сортировке вставки. Одна операция вставки будет стоить вам O (n).Использование кучи для управления вашим массивом сделает стоимость ввода O (log n), но может быть медленнее для небольших размеров массива. См. http://en.wikipedia.org/wiki/Binary_heap