Более быстрый способ создания отсортированной копии вектора

Question

Учитывая несортированный вектор в качестве источника, цель состоит в том, чтобы создать отсортированную копию как можно быстрее.Есть две возможности: 1. создать векторную копию, затем отсортировать ее 2. или вставлять каждый элемент один за другим, чтобы постепенно наращивать отсортированный вектор.

Что теоретически быстрее?

Answer 1

Ответы можно найти в следующей приятной конференции: короче, это зависит от размера вектора.Следовательно, комментарий Питера - лучший. CppCon 2018: Фредерик Тинго «Маленький порядок: изучение алгоритмов сортировки STL»

Answer 2

Этот вопрос имеет очень мало общего с C ++ (за исключением использования слова "вектор", которое также существует в некоторых других языках).Поскольку это выглядит как упражнение, я действительно рекомендую написать программу для его проверки:

1. write a program that builds a vector of random N integers, v1
2. copy the vector to v2, via std::copy
3. time how long it takes to use insertion-sort (option 2 above), using a loop
4. time how long std::sort(v2, v2.begin(), v2.end()) takes

Вы можете рассчитывать время, используя разные таймеры, либо старый <ctime> заголовок, либо более новый <chrono>.См. этот ответ для альтернатив.

Вы должны обнаружить, что для небольших размеров N цикл с шага 3 быстрее или эквивалентен шагу 4 - и с несколькими сотнями вперед, std::sort становится все лучше и лучше.Добро пожаловать в асимптотическую сложность и big-o нотацию !