Algorithms SkillFactory

Appearance

Поразрядная сортировка. ​

Алгоритм ​

Например, чтобы понять, как отсортировать числа [137137105157, 24395739293, 474290561035, 5, 276, 42], алгоритм сделает так:

  1. Подготовка. Алгоритм узнает, сколько элементов в массиве — 6.
  2. Узнает, сколько разрядов у самого длинного числа — 12 (возьмёт «длину» числа 137137105157).
  3. Создаст промежуточный массив с 10 пустыми ячейками (10 — выбранное основание системы счисления).
  4. Первый разряд. Найдёт все значения первого разряда в каждом числе → 2, 3, 5, 6 и 7.
  5. Положим соответствующие числа в ячейки под этими номерами
    [[], [], [42], [24395739293], [], [474290561035, 5], [276], [137137105157], [], []].
  6. Заменит содержимое исходного массива этими непустыми значениями: [42, 24395739293, 474290561035, 5, 276, 13713710515.
  7. Второй разряд. Теперь то же самое сделает со вторым разрядом: найдем все значения второго разряда в каждом числе → 0, 3,4,5, 7,9. Ноль — потому что второй разряд у пятёрки — нулевой, 5 = 05.
  8. Положим соответствующие числа в ячейки под этими номерами
    [[5], [], [], [474290561035], [42], [137137105157], [], [276], [], [24395739293]].
  9. Заменит содержимое исходного массива этими непустыми значениями: [5, 474290561035, 42, 137137105157, 276, 24395739293].
  10. Третий разряд. То же самое сделает с третьим разрядом: посмотрим на значение числа, стоящего на третьем месте справа налево: 0, 1, 2.
  11. Положим соответствующие числа в ячейки под этими номерами: [[5, 474290561035, 42], [137137105157], [276, 24395739293], [], [], [], [], [], [], []].
  12. Заменим содержимое массива этими непустыми значениями: [5, 474290561035, 42, 137137105157, 276, 24395739293].
  13. Четвёртый разряд. То же самое сделает с четвёртым разрядом: посмотрим на значение числа, стоящего на третьем месте справа налево: 0 (количество тысяч у первых трёх маленьких чисел), 1, 5 и 9.
  14. Положим соответствующие числа в ячейки под этими номерами: [[5, 42, 276], [474290561035], [], [], [], [137137105157], [], [], [], [24395739293]].
  15. Заменим содержимое массива этими непустыми значениями: [5, 42, 276, 474290561035, 137137105157, 24395739293].
  16. И так далее. Сделает так ещё восемь раз.
  17. В итоге получим отсортированный массив без сравнений: [5, 42, 276, 24395739293, 137137105157, 474290561035].
python
def radix_sort(arr):  
    max_digits = max([len(str(x)) for x in arr])  
	  
    base = 10  
	  
    bins = [[] for _ in range(base)]  
	  
    for i in range(0, max_digits):  
        for x in arr:  
            digit = (x // base ** i) % base  
            bins[digit].append(x)  
        arr = [x for queue in bins for x in queue]  
        bins = [[] for _ in range(base)]  
	  
    return arr

[1245, 763, 4, 70, 11, 2553]

1: [70, 11, 763, 2553, 4, 1245] 2: [4, 11, 1245, 2553, 763, 70] 3: [4, 11, 70, 1245, 2553, 763] 4: [4, 11, 70, 763, 1245, 2553]