Радикс Сортировка в Java
Узнайте об алгоритме сортировки Radix и о реализации его на Java.
1. Введение
В этом учебнике мы узнаем о Radix Sort, проанализируем его производительность и посмотрим на его реализацию.
Здесь мы сосредоточены на использовании Radix Sort для сортировки интеграторов, но это не ограничивается только числами. Мы можем использовать его для сортировки других типов, таких как Струна, тоже.
Для того, чтобы все было просто, мы сосредоточимся на десятичной системе, в которой цифры выражаются в базовом (радиксе) 10.
2. Обзор алгоритма
Сорт Radix является алгоритмом сортировки, который сортирует числа на основе позиций их цифр. В основном, он использует значение места цифр в номере. В отличие от большинства других алгоритмов сортировки, таких как Слияние Сортировка , Вставка Сортировка , Пузырь Сортировать , он не сравнивает цифры.
Сорт Radix использует стабильный алгоритм сортировки в качестве подпрограммы для сортировки цифр. Мы использовали вариацию подсчета рода в качестве подпрограммы здесь, которая использует радикс для сортировки цифр в каждой позиции. Сортировка подсчета является стабильным алгоритмом сортировки, и он хорошо работает на практике.
Сорт Radix работает путем сортировки цифр от наименее значимого Digit (LSD) до наиболее значимого Digit (MSD). Мы также можем внедрить сортировку Radix для обработки цифр из MSD.
3. Быстрый пример
Давайте посмотрим, как это работает с примером. Рассмотрим следующий массив:
Итерация 1:
Мы сортим этот массив, обработав цифры из ЛСД и двигаясь в направлении MSD.
Итак, давайте начнем с цифр в одном месте:
После первой итерации массив теперь выглядит так:
Обратите внимание, что цифры были отсортированы в соответствии с цифрами в одном месте.
Итерация 2:
Давайте перейдем к цифрам в десятки место:
Теперь массив выглядит так:
Мы видим, что номер 7 занял первую позицию в массиве, так как он не имеет никакой цифры в десятки месте. Мы могли бы также думать об этом, как имеющие 0 в десятки месте.
Итерация 3:
Давайте перейдем к цифрам в сотни позиции:
После этой итерации массив выглядит так:
И алгоритм останавливается здесь, со всеми элементами отсортированы.
4. Осуществление
Давайте теперь рассмотрим реализацию.
Алгоритм работает, выясывая максимальное количество в массиве, а затем вычисляя его длину. Этот шаг помогает нам гарантировать, что мы выполняем подпрограмму для каждого значения места.
Например, в массиве No 7, 37, 68, 123, 134, 221, 387, 468, 769 , максимальное число 769 и его длина 3.
Итак, мы итерировать и применять подпрограмму трижды на цифры в каждой позиции:
void applyCountingSortOn(int[] numbers, int placeValue) < int range = 10 // decimal system, numbers from 0-9 // . // calculate the frequency of digits for (int i = 0; i < length; i++) < int digit = (numbers[i] / placeValue) % range; frequency[digit]++; >for (int i = 1; i < range; i++) < frequency[i] += frequency[i - 1]; >for (int i = length - 1; i >= 0; i--) < int digit = (numbers[i] / placeValue) % range; sortedValues[frequency[digit] - 1] = numbers[i]; frequency[digit]--; >System.arraycopy(result, 0, numbers, 0, length); >
В подпрограмме мы использовали радикс (диапазон) подсчитать возникновение каждой цифры и приращение ее частоты. Таким образом, каждый бункер в диапазоне от 0 до 9 будет иметь некоторое значение в зависимости от частоты цифр. Затем мы используем частоту для позиционирования каждого элемента в массиве. Это также помогает нам свести к минимуму пространство, необходимое для сортировки массива.
Теперь давайте проверить наш метод:
@Test public void givenUnsortedArray_whenRadixSort_thenArraySorted() < int[] numbers = ; RadixSort.sort(numbers); int[] numbersSorted = ; assertArrayEquals(numbersSorted, numbers); >
5. Radix Сортировать против подсчета Сортировать
В подпрограмме длина частотный массив 10 (0-9). В случае Подсчета Сортировка, мы не используем диапазон . Длина частотный массив будет максимальное число в массиве No 1. Таким образом, мы не делим их на бункеры, в то время как Radix Sort использует бункеры для сортировки.
Подсчет сортировки является довольно эффективным, когда длина массива не намного меньше максимального значения в массиве, в то время как Radix Sort позволяет большие значения в массиве.
6. Сложность
Производительность Radix Sort зависит от стабильного алгоритма сортировки, выбранного для сортировки цифр.
Здесь мы использовали Radix Sort для сортировки массива n номера в базовом b . В нашем случае база 10. Мы применили Счетную d времена, когда d означает количество цифр. Таким образом, сложность времени Radix Sort становится O(d q (n q b)) .
Сложность пространства О(н и б) так как мы использовали вариацию Counting Sort в качестве подпрограммы здесь.
7. Заключение
В этой статье мы описали алгоритм сортировки Radix и проиллюстрировали, как его реализовать.
Как обычно, реализации кода доступны более на Github .
Radix Sort Java Program and Algorithm
This tutorial is about radix sort java program and algorithm.
Here is a very basic and detailed description of algorithm that we follow to implement the radix sort in java. We mostly rely on the place value of digits to sort it out in the given list. So, our first basic task is to find out the number with maximum length and then iterate the whole loop over the length of the digit.
Next we arrange every number considering 1s place value, 10s place value, 100s place value and so on till the length of the maximum digit.
Radix Sort Java Algorithm
1. Find the length of the number that has maximum number of digits.
2. Initialize i=0, Repeat the below procedure till the length equals i.
3. Fill the bucket with all the digits in ith position.
4. Sort out the digits according to the order.
5. If length=i, i=i*10, goto to step 3. Else go to step 5
6. Print the sorted array.
Complexity
The complexity of Radix Sort is far better than that of bubble sort and some other sorting techniques. It is as shown below depends on d and b.
O (d*(n+b))
d is digits in input integers.
b is the base for representing numbers.
Explanation
Let us start the implementation of the program. First we define a class named RadixSort and obviously it has only one method named sort to sort the numbers given. This function is the central part of discussion and as always, we take the inputs for the user using the main function and pass it on to the sorting function. The below code snippet shows it.