Алгоритм поразрядной сортировки в структуре данных

Что такое алгоритм поразрядной сортировки?

Поразрядная сортировка — это алгоритм несравнительной сортировки. Он работает путем группировки отдельных цифр элементов, подлежащих сортировке. Затем используется метод стабильной сортировки для организации элементов по их основанию. Это линейный алгоритм сортировки.

Процесс сортировки включает в себя следующиеwing свойства:

  • Нахождение максимального элемента и получение количества цифр этого элемента. Это дает нам количество итераций, которым будет следовать процесс сортировки.
  • Группируйте отдельные цифры элементов в одной и той же значимой позиции на каждой итерации.
  • Процесс группировки начнется с младшей значащей цифры и закончится самой старшей цифрой.
  • Сортировка элементов по цифрам в этой значимой позиции.
  • Поддержание относительного порядка элементов, имеющих одинаковое значение ключа. Это свойство поразрядной сортировки делает ее стабильной.

Последняя итерация даст нам полностью отсортированный список.

Работа алгоритма поразрядной сортировки

Работа алгоритма поразрядной сортировки
Список целых чисел для сортировки

Давайте попробуем отсортировать список целых чисел на рисунке выше в порядке возрастания, используя алгоритм поразрядной сортировки.

Вот шаги для выполнения процесса поразрядной сортировки:

Шаг 1) Определите элемент с максимальным значением в списке. В данном случае это 835.

Шаг 2) Вычислите количество цифр максимального элемента. Число 835 состоит ровно из 3 цифр.

Шаг 3) Определите количество итераций на основе шага 2. Число 835 состоит из 3 цифр, то есть количество итераций будет равно 3.

Шаг 4) Определите основу элементов. Поскольку это десятичная система, основанием будет 10.

Шаг 5) Запустите первую итерацию.

а) Первая итерация

Работа алгоритма поразрядной сортировки
Сортировка по последней цифре

На первой итерации мы рассматриваем единичное значение каждого элемента.

Шаг 1) Измените целое число на 10, чтобы получить единичное место элементов. Например, 623 по модулю 10 дает нам значение 3, а 248 по модулю 10 дает нам 8.

Шаг 2) Используйте сортировку подсчетом или любую другую стабильную сортировку, чтобы упорядочить целые числа в соответствии с их младшей значащей цифрой. Как видно из рисунка, 248 попадет в 8-е ведро. 623 попадет в 3-е ведро и так далее.

После первой итерации список теперь выглядит так.

Работа алгоритма поразрядной сортировки
Список после первой итерации

Как видно из приведенного выше рисунка, список еще не отсортирован и для полной сортировки требуется больше итераций.

б) Вторая итерация

Работа алгоритма поразрядной сортировки
Сортировка по цифрам в десятках

В этой итерации мы будем рассматривать цифру в позиции 10.th место для процесса сортировки.

Шаг 1) Разделим целые числа на 10. 248 разделить на 10 даст 24.

Шаг 2) Измените результат шага 1 на 10. 24 mod 10 дает нам 4.

Шаг 3) Выполните шаг 2 из предыдущей итерации.

После второй итерации список теперь выглядит так

Работа алгоритма поразрядной сортировки
Список после второй итерации

На приведенном выше рисунке видно, что список все еще не отсортирован полностью, поскольку он еще не расположен в порядке возрастания.

в) Третья итерация

Работа алгоритма поразрядной сортировки
Сортировка по цифрам в сотнях мест

На последней итерации мы хотим получить самую старшую цифру. В данном случае это 100th место для каждого целого числа в списке.

Шаг 1) Разделим целые числа на 100… 415, разделенное на 100, даст нам 4.

Шаг 2) Измените результат шага 1 на 10. 4 mod 10 снова дает нам 4.

Шаг 3) Выполните шаг 3 из предыдущей итерации.

Работа алгоритма поразрядной сортировки
Список после третьей итерации

Как мы видим, список теперь отсортирован по возрастанию. Последняя итерация завершена, и процесс сортировки завершен.

Псевдокод алгоритма поразрядной сортировки

Вот псевдокод алгоритма поразрядной сортировки.

radixSortAlgo(arr as an array)
  Find the largest element in arr
  maximum=the element in arr that is the largest
  Find the number of digits in maximum
  k=the number of digits in maximum 
  Create buckets of size 0-9 k times
for j -> 0 to k
  Acquire the jth place of each element in arr. Here j=0 represents the least significant digit.
  Use a stable sorting algorithm like counting sort to sort the elements in arr according to the digits of the elements in the jthplace
   arr = sorted elements

Программа C++ для реализации поразрядной сортировки

#include <iostream>
using namespace std;
// Function to get the largest element in an array
int getMaximum(int arr[], int n) {
  int maximum = arr[0];
  for (int i = 1; i < n; i++) {
    if (maximum < arr[i]) maximum = arr[i];
  }
  return maximum;
}
// We are using counting sort to sort the elements digit by digit
void countingSortAlgo(int arr[], int size, int position) {
  const int limit = 10;
  int result[size];
  int count[limit] = {0};
  // Calculating the count of each integers
  for (int j = 0; j < size; j++) count[(arr[j] / position) % 10]++;
  // Calculating the cumulative count
  for (int j = 1; j < limit; j++) {
    count[j] += count[j - 1];
  }
  // Sort the integers
  for (int j = size - 1; j >= 0; j--) {
    result[count[(arr[j] / position) % 10] - 1] = arr[j];
    count[(arr[j] / position) % 10]--;
  }
  for (int i = 0; i < size; i++) arr[i] = result[i];
}
// The radixSort algorithm
void radixSortAlgo(int arr[], int size) {
  // Get the largest element in the array
  int maximum = getMaximum(arr, size);
  for (int position = 1; maximum / position > 0; position *= 10)
    countingSortAlgo(arr, size, position);
}
// Printing final result
void printResult(int arr[], int size) {
  for (int i = 0; i < size; i++) {
    cout << arr[i] << " ";
  }
  cout << endl;
}
int main() {
  int arr[] = {162, 623, 835, 415, 248};
  int size = sizeof(arr) / sizeof(arr[0]);
  radixSortAlgo(arr, size);
  printResult(arr, size);
}

Вывод:

162 248 415 623 835

Программа Python для алгоритма поразрядной сортировки

#Radix Sort using python
def countingSortAlgo(arr, position):
    n = len(arr)
    result = [0] * n
    count = [0] * 10  # Calculating the count of elements in the array arr
    for j in range(0, n):
        element = arr[j] // position
        count[element % 10] += 1  # Calculating the cumulative count
    for j in range(1, 10):
        count[j] += count[j - 1]  # Sorting the elements
    i = n - 1
    while i >= 0:
        element = arr[i] // position
        result[count[element % 10] - 1] = arr[i]
        count[element % 10] -= 1
        i -= 1
    for j in range(0, n):
        arr[j] = result[j]


def radixSortAlgo(arr):  # Acquiring the largest element in the array
    maximum = max(arr)  # Using counting sort to sort digit by digit
    position = 1
    while maximum // position > 0:
        countingSortAlgo(arr, position)
        position *= 10


input = [162, 623, 835, 415, 248]
radixSortAlgo(input)
print(input)

Вывод:

[162,248,415,623,835]

сplexанализ эффективности поразрядной сортировки

Есть два типа ком.plexстоит учитывать, космическая коммуникацияplexгород и времяplexность.

  • Космос комplexity: O(n+b), где n — размер массива, а b — рассматриваемая база.
  • команда сplexity: O(d*(n+b)), где d — количество цифр самого большого элемента массива.

Космическая связьplexСущность поразрядной сортировки

Две особенности космической связи, на которых стоит сосредоточитьсяplexность

  • Количество элементов в массиве, n.
  • Основа для изображения элементов, b.

Иногда эта база может превышать размер массива.

Общий комplexтаким образом, ность равна O(n+b).

Фоллоwing свойства элементов в списке могут сделать пространство поразрядной сортировки неэффективным:

  • Элементы с большим количеством цифр.
  • База элементов большая, как 64-битные числа.

Время КомplexСущность поразрядной сортировки

Вы можете использовать сортировку подсчетом как подпрограмму, так как каждая итерация будет выполнятьсяе O(n+b) время. Если существует d итераций, общее время выполнения становится О(d*(n+b)). Здесь «О» означает ком.plexфункция.

Линейность поразрядной сортировки

Поразрядная сортировка является линейной, если

  • d является константой, где d — количество цифр наибольшего элемента.
  • b не намного больше по сравнению с n.

Сравнение поразрядной сортировки с другими сравнительными алгоритмами

Как мы видели, сортировка Radix complexКачество основано на размере слова или числа. У него будет тот же комplexдля среднего и наилучшего случаев. И это O(d*(n+b)). Кроме того, он различается в зависимости от метода сортировки, который вы используете посередине. Например, вы можете использовать сортировку подсчетом или быструю сортировку для алгоритма промежуточной сортировки внутри поразрядной сортировки.

Применение алгоритма поразрядной сортировки

Важные применения поразрядной сортировки:

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