Почему сортировка вставкой работает быстрее сортировки выбором в самом сложном случае?

Question

[Qubc]

Число сравнений в сортировке вставкой зависит от упорядоченности элементов, что выгодно отличает её от сортировки выбором, это понятно. Но в самом худшем случае (массив 5 4 3 2 1 нужно отсортировать в 1 2 3 4 5), когда переставлять нужно каждый элемент - этот бонус не работает, ведь так ? Я хочу посчитать это численно - и получается какой - то бред.
Число копирований (без учета копирований индексов) у выбора: N * 3
Число копирований у перестановки : N + N + N * (N - 1) / 2
То есть копирований будет даже больше, а работает всё равно быстрее.
Ну что я считаю не так ?

void select () {
    for (int outer = nElems - 1; outer > 0; --outer) {
        int index_max = outer;
        for (int inner = outer - 1; inner >= 0; --inner) {
            if (a [ inner ] > a [ index_max ]) {  // n_comp = N * (N-1) / 2
                index_max = inner;
            }
        }

        int temp = a [ outer ]; // N 
        a [ outer ] = a [ index_max ]; // N
        a [ index_max ] = temp; // N
    }
}

void insert () {
    for (int outer = 1; outer < nElems; ++outer) {
        int temp = a [ outer ];// N 
        int inner = outer;
        for (; inner > 0 && a [ inner - 1 ] > temp; --inner) {// n_comp = N * (N-1) * 2
            a [ inner ] = a [ inner - 1 ]; // n_copy = N * (N-1) / 2
        }
        a [ inner ] = temp; //  N 
    }
}

Answer 1

[rPman]

Возможно вступают особенности оптимизации выполнения на процессорах с маленьким размером массива (кеши, предсказание ветвления), например если массив int порядка 1000 элементов у меня тесты это и показывают insert быстрее или равный по скорости, а 10к..1000к уже заметно медленнее

а тут и 1000 различия есть https://www.mycompiler.io/view/1CQUKga8um2

Comments

[Qubc]

Скажи пожалуйста, но сами сложности я правильно посчитал?

[rPman]

оба твоих алгоритма O(N^2), да N*(N-1)/2
insert вынужден двигать весь массив по одному (записи), а select только ищет максимальное число (чтения) что быстрее даже по техническим причинам

[Qubc]

rPman, я имею ввиду именно количество копирований у перестановки : N + N + N * (N - 1) / 2 , верно?

[Qubc]

rPman, спасибо за код, я тоже пробовал большие значения, но будто не заметил что с большими числами разница действительно видна.

[rPman]

да но N+N+N это константы, их опускают при подсчете сложности

[Qubc]

rPman, понятно, просто я затупил, спасибо

Answer 2

[mayton2019]

Какого размера у тебя массивы? Там для маленьких - вообще теоретическая формула не работает.
Видимо в силу когерентности кеша тупые и жлобские алгоритмы работают лучше чем умные и сложные.

Я думаю что теоретическая оценка начинает играть роль тогда, когда массив реально в несколько крат
превышает хотя-бы кеш L3.

Я для мелких массивов (2,3 элемента) сортировка пузырем вполне себе делает минимум операций.
Ее даже можно хардкодить размоткой циклов.

Есть также вопросы на собеседовании для джунов (Java) которые практически позволяют нагнуть новичка
показав ему на практике что вставка примитива в ArrayList (массив) работает быстрее чем вставка в LinkedList.

Опять-же этот эффект заметен на малых размерах массивов.

Comments

[Qubc]

Какого размера у тебя массивы? Там для маленьких - вообще теоретическая формула не работает.

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

Вставка в массив, в котором элементы сдвигаются? Работает быстрее чем в односвязный одно-конечный (single-ended) список? В каких условиях? Интересно, не понял.

[mayton2019]

Qubc, точных условий я не помню. Но они примерно такие-же как и в топике. На малых объемах данных - простые алгоритмы и стурктуры данных работают всегда лучше чем сложные.

[Qubc]

mayton2019, а, я понял, спасибо.