Сортировка аппроксимацией :: Proxmap Sort

Другие алгоритмы, использующие принципы приблизительного распределения и последующей вставки - флеш-сортировка и сортировка царя Соломона.

Визуализация похожа на сортировку «Американский флаг».

  1. Применяем аппроксимирующую функцию к каждому элементу, определяя, какому хиту соответствует очередной элемент.
  2. Таким образом для каждого хита можем подсчитать количество элементов, соответствующих данному хиту.
  3. Зная количества элементов для всех хитов, определяем локализации хитов (границы слева) в массиве.
  4. Зная локализации хитов, определяем локализацию каждого элемента.
  5. Определив локализацию элемента, пытаемся вставить его на своё место в массиве. Если место уже занято, то или сдвигаем соседей вправо (если элемент меньше их), чтобы освободить место для элемента. Или правее вставляем сам элемент (если он больше соседей).

Ссылки

Подсчёт с приблизительным распределением — чаще всего переизобретаемая сортировка

Proxmap sort