Введение в Radix Sort

Основание (или основание ) - это количество цифр, используемых для представления чисел в позиционной системе счисления . Для двоичной системы основание системы счисления равно 2 (в ней используются только две цифры - 0 и 1). Для десятичной системы основание системы счисления - 10 (для представления всех чисел используются десять цифр - от 0 до 9).

Позиционная система счисления - это, проще говоря, система записи чисел, где вес (или значение) цифры определяется ее положением. Например, в числе 123 1 имеет большее значение, чем 3 потому что оно находится в позиции, обозначающей сотни, а 2 - в десятках.

Radix Sort может использоваться для лексикографической сортировки многих типов данных - целых чисел, слов, электронных писем, но в основном используется для сортировки коллекций целых чисел и строк (которые сопоставлены с соответствующими целочисленными ключами).

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

Алгоритмы сравнительной сортировки имеют лучшую временную сложность O (nlogn) , которая сравнительно хуже, чем время линейного выполнения ( O (n + k) ) несравнительных алгоритмов.

Например, пусть n будет количеством элементов для сортировки, а k - диапазоном допустимых значений элементов.

Сортировка подсчетом (популярный несравнительный алгоритм) имеет сложность O(n+k) когда k находится в диапазоне от 1 до 1..n . Но если элементы 1..n² диапазоне от 1..n², то сложность возрастает до O(n²) , что хуже, чем у любого алгоритма сравнительной сортировки.

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

Идея Radix Sort состоит в том, чтобы обновить сортировку с подсчетом, чтобы она сохраняла линейную временную сложность, даже если диапазон значений элементов значительно превышает количество элементов.

Фактически, Radix Sort по своей сути использует подсчетную сортировку в качестве основной подпрограммы с несколькими настройками для преодоления проблем, возникающих при увеличении диапазона значений элементов.

• Подсчет алгоритма сортировки
• Зачем использовать подсчетную сортировку?
• Как работает подсчетная сортировка?
• Реализация сортировки с подсчетом
• Подсчет сложности сортировки
• Алгоритм сортировки по основанию
• Реализация Radix Sort
• Сложность сортировки по основанию

Подсчет алгоритма сортировки

Чтобы получить представление о Radix Sort, нам нужно сначала углубиться в Counting Sort, реализовать ее и наблюдать падение с увеличением количества значений элементов.

Зачем использовать подсчетную сортировку в радикальной сортировке?

Подсчет рода является стабильным, алгоритмом несравнительной сортировки, и она в основном используются для сортировки целочисленных массивов. Все эти характеристики важны для использования в Radix Sort. Вы можете использовать другие алгоритмы в качестве подпрограммы, если они имеют эти характеристики, однако сортировка с подсчетом является наиболее естественным соответствием.

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

{.ezlazyload}

Алгоритмы несравнительной сортировки обычно имеют линейную сложность, поэтому они меньше влияют на сложность Radix Sort.

Как работает счетная сортировка?

Давайте посмотрим на несортированный целочисленный массив, который мы отсортируем с помощью Counting Sort:

 I = [2, 2, 0, 6, 1, 9, 9, 7] 

Сортировка с подсчетом работает путем подсчета количества элементов , соответствующих определенному значению ключа , а затем вычисляет позиции каждого ключа.

Прежде всего, мы найдем максимальный элемент во входном массиве - max = 9 .

Затем мы создадим вспомогательный массив с max+1 элементами. Это массив счетчика ( C ), который будет использоваться для хранения количества вхождений каждого элемента во входном массиве .

Первоначально все счетчики инициализируются равными 0:

 C = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0] # Count array 
 #indices: 0 1 2 3 4 5 6 7 8 9 

Теперь нам нужно пройти следующие шаги:

1. Пройдите по входному массиву и увеличьте соответствующий счетчик для каждого элемента на 1

Например, если мы встречаем элемент со значением 2 во входном массиве ( I ), мы добавляем 1 к элементу с индексом 2 в массиве count :

 I = [2, 2, 0, 6, 1, 9, 9, 7] # The first element is 2 
 ^ 
 
 C = [0, 0, 1, 0, 0, 0, 0, 0, 0, 0] # We increase count of 2nd element by 1 
 #indices: 0 1 2 3 4 5 6 7 8 9 

После этого шага массив count будет хранить количество вхождений каждого элемента во входном массиве :

 C = [1, 1, 2, 0, 0, 0, 1, 1, 0, 2] 
 #indices: 0 1 2 3 4 5 6 7 8 9 
 
 # Element 0 has 1 occurrence 
 # Element 1 has 1 occurrence 
 # Element 2 has 2 occurrences 
 # Element 3 has no occurrences... 

2. Для каждого элемента в массиве count просуммируйте его значение со значением всех его предыдущих элементов, а затем сохраните это значение как значение текущего элемента:

 C = [1, 2, 4, 4, 4, 4, 5, 6, 6, 8] 
 #indices: 0 1 2 3 4 5 6 7 8 9 
 # Element 0 = 1 
 # Element 1 = 1 + 1 
 # Element 2 = 1 + 1 + 2 
 # Element 3 = 1 + 1 + 2 + 0 
 #... 

Таким образом, мы сохраняем совокупную сумму элементов массива count на каждом шаге.

3. Вычислить позицию элемента на основе значений массива count.

Чтобы сохранить эту отсортированную последовательность, нам нужно создать новый массив. Назовем его выходным массивом ( O ) и инициализируем k нулями, где k - количество элементов во входном массиве :

 O = [0, 0, 0, 0, 0, 0, 0, 0] // Initialized output array 
 #indices: 0 1 2 3 4 5 6 7 

Для каждого элемента I[i] (начиная с конца) во входном массиве :

1. Найдите в массиве count индекс, равный значению текущего элемента I[i]
   • Это элемент C[j] где j=I[i]
2. Вычтите 1 из значения C[i] .
   • Теперь у нас есть newValue = C[i]-1
3. Сохраните I[i] в O[newValue]
4. Обновите C[i] newValue

{.ezlazyload}

В конце концов, выходной массив содержит отсортированные элементы входного массива!

Реализация сортировки с подсчетом в Python

Теперь, разобравшись со всем этим, давайте продолжим реализацию Counting Sort в Python:

 def countingSort(inputArray): 
 # Find the maximum element in the inputArray 
 maxEl = max(inputArray) 
 
 countArrayLength = maxEl+1 
 
 # Initialize the countArray with (max+1) zeros 
 countArray = [0] * countArrayLength 
 
 # Step 1 -> Traverse the inputArray and increase 
 # the corresponding count for every element by 1 
 for el in inputArray: 
 countArray[el] += 1 
 
 # Step 2 -> For each element in the countArray, 
 # sum up its value with the value of the previous 
 # element, and then store that value 
 # as the value of the current element 
 for i in range(1, countArrayLength): 
 countArray[i] += countArray[i-1] 
 
 # Step 3 -> Calculate element position 
 # based on the countArray values 
 outputArray = [0] * len(inputArray) 
 i = len(inputArray) - 1 
 while i >= 0: 
 currentEl = inputArray[i] 
 countArray[currentEl] -= 1 
 newPosition = countArray[currentEl] 
 outputArray[newPosition] = currentEl 
 i -= 1 
 
 return outputArray 
 
 inputArray = [2,2,0,6,1,9,9,7] 
 print("Input array = ", inputArray) 
 
 sortedArray = countingSort(inputArray) 
 print("Counting sort result = ", sortedArray) 

Выполнение приведенного выше кода даст нам следующий результат:

 Input array = [2, 2, 0, 6, 1, 9, 9, 7] 
 Counting sort result = [0, 1, 2, 2, 6, 7, 9, 9] 

Подсчет сложности сортировки

Временная сложность сортировки с подсчетом составляет O(n+k) , где n

• количество элементов во входном массиве , а k - значение max элемента в массиве.

Проблема возникает, когда значение самого большого элемента значительно превышает количество элементов в массиве. Когда k приближается к n² , временная сложность приближается к O(n²) , что является ужасной временной сложностью для алгоритма сортировки.

Вот тут-то и вступает в действие Radix Sort.

Алгоритм сортировки по основанию

Вместо подсчета элементов по их отдельному значению ключа - Radix Sort группирует цифры по их позиционному значению и выполняет сортировку с подсчетом в каждой группе. Начальная позиция может варьироваться - LSD (наименьшие значащие цифры) или MSD (наиболее значимые цифры) являются двумя распространенными, и, соответственно, эти варианты Radix Sort называются LSD Radix Sort и MSD Radix Sort.

Пусть I = [2, 20, 61, 997, 1, 619] будет входным массивом, который мы хотим отсортировать:

{.ezlazyload}

Мы сосредоточимся на LSD Radix Sort .

Алгоритм сортировки по основанию

Шаги, предпринятые Radix Sort, довольно просты:

1. Найдите максимальный элемент во входном массиве - max = 997
2. Найдите количество цифр в элементе max D = 3
3. Инициализировать значение места для наименее значимого места - placeVal = 1
4. Для D раз:
   1. Выполните сортировку с подсчетом по текущему разряду
   2. Перейти к следующему placeVal умножив placeVal на 10

{.ezlazyload}

Реализация Radix Sort в Python

И, наконец, разобравшись с этим, давайте реализуем Radix Sort в Python:

 def countingSortForRadix(inputArray, placeValue): 
 # We can assume that the number of digits used to represent 
 # all numbers on the placeValue position is not grater than 10 
 countArray = [0] * 10 
 inputSize = len(inputArray) 
 
 # placeElement is the value of the current place value 
 # of the current element, eg if the current element is 
 # 123, and the place value is 10, the placeElement is 
 # equal to 2 
 for i in range(inputSize): 
 placeElement = (inputArray[i] // placeValue) % 10 
 countArray[placeElement] += 1 
 
 for i in range(1, 10): 
 countArray[i] += countArray[i-1] 
 
 # Reconstructing the output array 
 outputArray = [0] * inputSize 
 i = inputSize - 1 
 while i >= 0: 
 currentEl = inputArray[i] 
 placeElement = (inputArray[i] // placeValue) % 10 
 countArray[placeElement] -= 1 
 newPosition = countArray[placeElement] 
 outputArray[newPosition] = currentEl 
 i -= 1 
 
 return outputArray 
 
 def radixSort(inputArray): 
 # Step 1 -> Find the maximum element in the input array 
 maxEl = max(inputArray) 
 
 # Step 2 -> Find the number of digits in the `max` element 
 D = 1 
 while maxEl > 0: 
 maxEl /= 10 
 D += 1 
 
 # Step 3 -> Initialize the place value to the least significant place 
 placeVal = 1 
 
 # Step 4 
 outputArray = inputArray 
 while D > 0: 
 outputArray = countingSortForRadix(outputArray, placeVal) 
 placeVal *= 10 
 D -= 1 
 
 return outputArray 
 
 input = [2,20,61,997,1,619] 
 print(input) 
 sorted = radixSort(input) 
 print(sorted) 

Выполнение приведенного выше кода даст нам следующий результат:

 [2, 20, 61, 997, 1, 619] 
 [1, 2, 20, 61, 619, 997] 

Сложность сортировки по основанию

Как мы заявляли ранее, Radix Sort имеет линейную временную сложность . Если мы используем сортировку с подсчетом в качестве основной подпрограммы, сложность поразрядной сортировки составит O(d(n+k)) . Это потому, что мы выполняем сортировку с подсчетом d раз, а сложность самой сортировки с подсчетом составляет O(n+k) .

Заключение

Radix sort - отличный алгоритм сортировки, который можно использовать в некоторых конкретных случаях. Некоторые тесты даже показали, что поразрядная сортировка может выполняться до 3 раз быстрее, чем другие, более универсальные алгоритмы сортировки.

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

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