Истоки Radix sorting.

Как быть, если нужно отсортировать ну очень много значений? Отвечая на этот вопрос, один известный статистик и изобретатель придумал не только алгоритм, но и машину для его реализации. Больше не нужно было пробегать по всем значениями и сравнивать.

Radix sorting, или поразрядная сортировка, заключается в том, что мы сначала делим данные по разрядам, а потом сортируем их внутри каждого разряда. Процесс сортировки может начинаться как с младших (правых), так и со старших (левых) разрядов. Первый подход известен как LSD-сортировка (Least Significant Digit radix sort), второй — как MSD-сортировка (Most Significant Digit radix sort). 

В реальных задачах поразрядная сортировка часто оказывается быстрее алгоритмов сортировки на основе сравнений, но она не так эффективна для небольших наборов данных. Кстати, на разряды можно разделить не только числа, но и, например, строки для поразрядной сортировки. 

Появление radix sorting связывают с 1887 годом, когда Герман Холлерит подал патент на электромеханическую табуляционную машину для обработки перфокарт. Инновационный подход и такие машины использовались в ходе переписи населения США 1890 года, а позднее — и в Российской империи для аналогичных задач.

Истоки Radix sorting | Сетка — новая социальная сеть от hh.ru
repost

14

input message

напишите коммент

еще контент в этом сообществе

еще контент в этом соообществе

войдите, чтобы увидеть

и подписаться на интересных профи

в приложении больше возможностей

пока в веб-версии есть не всё — мы вовсю работаем над ней

сетка — cоциальная сеть для нетворкинга от hh.ru

пересекайтесь с теми, кто повлияет на ваш профессиональный путь