Бинго-сортировка :: Bingo Sort

Модификация простой сортировки выбором, позволяющая быстрее сортировать массивы, состоящие из неуникальных элементов.

Модификация

В неупорядоченной части запоминается не только максимальный элемент, но и определяется максимум для следующей итерации.

Это позволяет не искать их заново каждый раз повторяющиеся максимумы и ставить на своё место сразу как только максимум в очередной раз встретили в массиве.

Характеристики алгоритма

НазваниеБинго-сортировка (Bingo sort)
КлассСортировки выбором
УстойчивостьНет
СравненияДа
Сложность по времениХудшаяO(n2 / 2)
СредняяO(n2 / 2)
ЛучшаяO(n2 / 2)
Сложность по памятиОбщаяO(n)
ДополнительнаяO(1)

Ссылки

Сортировки выбором

Сортировка выбором

Selection sort