Время выполнения для вставки сортировки

Question

Время выполнения для вставки сортировки

for (int p=1; p < a.size(); p++) {
int tmp = a[p];
for(j=p; j>0 && tmp < a[j-1]; j--) {
a[j] = a[j-1];
}
a[j] = tmp;
}

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

Внешний цикл проходит через массив. Итак, он работает (n раз). На)
int tmp=a[p] —- Это утверждение выполняется n раз. На)
Внутренний цикл выполняется (1 + 2 + 3 + 4 + 5 + 6 + …. + n-1) раз. O (N ^ 2)
a[j]= tmp——— Этот оператор выполняется n раз. На)

Я не уверен, что делать после, чтобы найти время выполнения сортировки вставки?
Исправьте мою работу, если можете.
Спасибо.

1

c++c++11 insertion-sort sorting time-complexity

Решение

Другие решения

Внешний цикл выполняется n раз.

Каждый прогон внутреннего цикла выполняется где-то между 0 и p-1 раз, где p изменяется от 0 до n. В худшем случае он будет выполняться p-1 раз. Если p изменяется от 0 до n, то в среднем p равно n / 2. Таким образом, сложность наихудшего случая для внутреннего цикла O (p-1) = O (n / 2-1) = O (n).

За исключением циклов, весь код — это O (1) (главное, код внутри внутреннего цикла), поэтому важны только циклы.

O (n) * O (n) = O (n ^ 2).

QED.

Это примерно тот анализ, который вы сами дали.

1

Источник

Accepted Answer

Вот двухстрочная реализация C ++ 11 сортировки вставкой

template< typename ForwardIterator, typename Compare = std::less<typename std::iterator_traits<ForwardIterator>::value_type> >
void insertion_sort(ForwardIterator first, ForwardIterator last, Compare cmp = Compare())
{
for (auto it = first; it != last; ++it) {
auto const insertion = std::upper_bound(first, it, *it, cmp);
std::rotate(insertion, it, std::next(it));
}
}

Алгоритм принимает ряд элементов (заданных двумя итераторами first а также last) и функция сравнения (по умолчанию используется встроенная функция operator< для элементов, указанных в).

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

После того, как он нашел точку вставки, он просто вращает два диапазона [insertion, it) а также [it, it+1), что означает перестановку текущего элемента в точку вставки. Это вращение является линейным по количеству элементов, которые были отсортированы до сих пор. Так как он вложен в основной цикл, общая сложность вставки сортировки является квадратичной, т.е. O(N^2), Ваш код включает в себя обмен и поиск точки вставки, но это не меняет сложности.

Обратите внимание, что когда входной диапазон уже отсортирован, точка вставки всегда будет равна элементу, на который указывает itи это означает, что std::rotate вообще ничего менять не надо. Достаточно умный и оптимизирующий компилятор должен быть в состоянии выполнить эту оптимизацию. Если это так, вставка сортировки в отсортированном диапазоне имеет линейную сложность.

Дается аналогичный двухстрочный подход к выбору сортировки Вот.

2