Бинго-сортировка :: Bingo Sort
Модификация простой сортировки выбором, позволяющая быстрее сортировать массивы, состоящие из неуникальных элементов.
Модификация
В неупорядоченной части запоминается не только максимальный элемент, но и определяется максимум для следующей итерации.
Это позволяет не искать их заново каждый раз повторяющиеся максимумы и ставить на своё место сразу как только максимум в очередной раз встретили в массиве.
Характеристики алгоритма
| Название | Бинго-сортировка (Bingo sort) | |
|---|---|---|
| Класс | Сортировки выбором | |
| Устойчивость | Нет | |
| Сравнения | Да | |
| Сложность по времени | Худшая | O(n2 / 2) |
| Средняя | O(n2 / 2) | |
| Лучшая | O(n2 / 2) | |
| Сложность по памяти | Общая | O(n) |
| Дополнительная | O(1) | |
Сортировка выбором