сортировка по фамилиям
сортировка по фамилиям учащихся пройдет внутри каждой из параллелей независимо от остальных.
Пример #2.
При игре в карты, получив после раздачи на руки N карт, игрок часто сортирует их по масти, и лишь затем - по старшинству, внутри каждого из четырех поднаборов независимо от остальных.
В обоих примерах вместо алгоритмов с квадратичной трудоемкостью O(N2) сначала работает разделение на несколько подмассивов, а затем каждый из них упорядочивается отдельно. Если таких подмассивов k, то общая трудоемкость составит O(N) + ?O(Ni2), где через Ni(i=1..k) обозначено количество элементов i-го подмассива. Заметим, что суммарная стоимость всех сортировок подмассивов уменьшается с ростом их числа k и, соответственно, уменьшением мощности каждого из них. Это обстоятельство свидетельствует о перспективности такого механизма.
Таким образом, располагая некоторой процедурой разделения вектора на подмассивы и, затем, их независимого упорядочивания, мы могли бы снизить общую трудоемкость сортировки
Индекс
Элементарные функции
Линейные уравнения
Нелинейные уравнения
Случайные числа
