MSD (самая значащая цифра) Radix Sort

В этой статье обсуждаются два типа сортировки по основанию:

• LSD Radix Sort: сортировка начинается с конца строки (наименее значащая цифра).
• MSD Radix Sort: сортировка начинается с начала строки (наиболее значимой цифры).

В этой статье задача состоит в том, чтобы обсудить сортировку по основанию MSD и сравнить ее с сортировкой по основанию LSD.

Подход: Идея состоит в том, чтобы выполнить следующие шаги для каждой цифры i , где значение i варьируется от старшей до младшей значащей цифры:

• Храните элементы в разных корзинах в соответствии с их i ^-й цифрой.
• Рекурсивно сортируйте каждое ведро, содержащее более одного элемента.

Сортировка по наименьшей значимой цифре :

• Идея состоит в том, чтобы сортировать целые числа фиксированной длины, MSD более эффективен, чем LSD, потому что ему не нужно проверять каждую цифру каждого целого числа:

LSD Radix Сортировка:

Сортировка по основанию MSD :

MSD Radix sort

• MSD можно использовать для сортировки строк переменной длины, в отличие от LSD. LSD должен быть стабильным, чтобы работать правильно, но MSD можно сделать стабильным или нестабильным, а MSD может работать со случайными строками.

• Сложность времени:
  • Сортировка LSD Radix: временная сложность в лучшем и худшем случае составляет O (N * M) , где M = длина самой длинной строки.
    MSD Radix sort: временная сложность в наилучшем случае равна O(N) , а временная сложность в наихудшем случае равна O(N*M) , где M = средняя длина строк.
• Вспомогательное пространство:
  • Сортировка LSD по основанию: O (N + B)
  • Сортировка по основанию MSD: O(N + MB ), где M = длина самой длинной строки, а B = размер основания (B=10 возможных чисел или B=256 символов или B=2 для двоичных).
• MSD использует рекурсию, поэтому требует больше места, чем LSD. Это означает, что MSD намного медленнее, чем LSD, при работе с несколькими входами.

Реализация MSD Radix Sort :

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

Ниже приведена реализация MSD Radix Sort с использованием связанного списка:

Использование метода Counting Sort(): эта реализация предназначена для строк, основанных на методе Counting sort(). Поскольку символ ASCII стиля C составляет 1 байт . Таким образом, массив размером 256 используется для подсчета вхождений символов и лексикографической сортировки строк.

Ниже представлена реализация MSD Radix Sort с использованием метода counting sort():

Для строки:

Для целого числа: