Какие самые быстрые алгоритмы сортировки без компьютера, вручную.
Макаронная сортировка.
Нужно отсортировать пачку макаронин по длине. Берем всю пачку макарон в руку и торцом ставим на поверхность стола, так, чтобы под действием силы тяжести каждая макаронина упёрлась в стол. Та макаронина, которая торчит над столом выше остальных — это самая длинная макаронина. Её легко выбрать из пачки, опуская раскрытую ладонь на эту пачку.
Сортировка заключается в том, что мы по одной вытаскиваем все макароны из пачки, начиная с самой длинной, и заканчивая самой короткой.
Сложность O(N) если физически вытаскивать макароны, либо O(1), если вместо вытаскивания довольствоваться тем, что после установки на стол вершки макаронин и *уже* упорядочены по высоте.
Соль в том, что в физическом мире мы не ограничены машиной тюринга / регистровой машиной, и степень параллелизма в ряде случаев может быть равна количеству подлежащих обработке объектов, что позволяет обрабатывать большие массивы объектов за константное время.
не знаю какой быстрый, но предполагаю, что большинство использует insertion sort
Для небольших обьемов сортировка вставками действительно неплоха, с большими трудно. Вручную проще сначала рассортировать на несколько групп, а затем каждую группу либо снова на подгруппы или сортировка вставками. Хз как таков алгоритм называется.
Отставить! Строй - установленное Уставом размещение военнослужащих, подразделений и воинских частей для их совместных действий в пешем порядке и на машинах. Строй может состоять из нескольких шеренг и колонн, с топологической, а не натуральной сортировкой.
если оставить в стороне выше упомянатую «макароную»(где хак использования того факта , что вселенная существенно «параллельна»)
то вроде как для последовательного исполнителя очень эффективна по разрядкая сортировка(от младшего к старшему разряду) ибо все итерации это процесс разбиение по группам по значениям различного критерия на каждой итерации
Насыпаешь в банку и начинаешь трясти. Нет, правда, где это возможно - быстро.
А так - (не помню как называется) - вправо большие, влево маленькие. Потом две получившиеся кучки делишь аналогично. Ну ,иногда процесс можно распараллелить.