LSD SORT

Info

LSD (Least Significant Digit) сортировка, также известная как сортировка по младшему разряду, является типом сортировки, который использует информацию о разрядах чисел для сортировки. Она работает путем сортировки чисел по каждому разряду, начиная с младшего.

Алгоритм

Алгоритм LSD сортировки может быть реализован для сортировки целых чисел или строк, представляющих числа. Ниже приведен алгоритм LSD сортировки для сортировки целых чисел.

1. Определите максимальное количество разрядов в числах.
2. Для каждого разряда от младшего к старшему:

• • Используйте подсчет для подсчета количества чисел с определенным значением в текущем разряде.
• • Измените подсчет, чтобы значения в нем представляли индексы в выходном массиве, чтобы позиции в массиве соответствовали порядку чисел.
• • Переместите числа из входного массива в выходной массив в соответствии с индексами, полученными в подсчете.
• • Обновите входной массив для следующей итерации.

3. Выходной массив будет отсортирован по LSD.