<commit_before>.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata:: Radix Sort
   :author: <NAME>
   :prerequisites: BinSort
   :topic: Sorting
   :short_name: RadixSort

.. _RadixSort:

.. include:: JSAVheader.rinc

.. index:: ! Radix Sort

Radix Sort
==========

The major problem with Binsort is that it does not work so well for a
large keyrange.
Fortunately, there is a way to keep the number of bins small and the
related processing relatively cheap while using the idea of binning
the records with similar key values.
Consider a sequence of records with keys in the range 0 to 99.
If we have ten bins available, we can first assign records to bins by
taking their key value modulo 10.
Thus, every key will be assigned to the
bin matching its rightmost decimal digit.
We can then take these records from the bins **in order**,
and reassign them to the bins
on the basis of their leftmost (10's place) digit.
We will define values in the range 0 to 9 to have a leftmost digit of
0.
In other words, assign the :math:`i`'th record from array ``A`` to
a bin using the formula ``A[i]/10``.
If we now gather the values from
the bins **in order**, the result is a sorted list.
We can see this process in the following visualization.

.. avembed:: AV/Sorting/radixLinkAV.html
   :showbutton: show
   :title: Linked Radix Sort

In this example, we have :math:`r=10` bins and key values in
the range 0 to :math:`r^2-1`.
The total computation is :math:`\Theta(n)`, because we look at each
record and each bin a constant number of times.
This is a great improvement over the simple Binsort where the number
of bins must be as large as the key range.
Note that the example uses :math:`r = 10` so as
to make the bin computations easy to visualize:
Records were placed into bins based on the value of first the
rightmost and then the leftmost decimal digits.
Any number of bins would have worked.
This is an example of a :dfn:`Radix Sort`, so called because the
bin computations are based on the :dfn:`radix` or the
:dfn:`base` of the key values.
This sorting algorithm can be extended to any number of
keys in any key range.
We simply assign records to bins based on the
keys' digit values working from the rightmost digit to the leftmost.
If there are :math:`k` digits, then this requires that we assign keys to
bins :math:`k` times.

Here is a practice exercise for placing keys into bins.

.. avembed:: Exercises/Sorting/RadixsortPRO.html
   :showbutton: hide
   :title: Radix Sort Practice

As with Mergesort, an efficient implementation of Radix Sort is
somewhat difficult to achieve.
In particular, we would prefer to sort an array of values and avoid
processing linked lists.
If we knew how  many values would be in each bin, then an auxiliary
array of size :math:`r` can be used to define these lengths and guide
us to were each one starts in the output array.
For example, if during the first pass the 0 bin will receive three
records and the 1 bin will receive five records, then we could simply
reserve the first three array positions for the 0 bin and the next
five array positions for the 1 bin.
Exactly this approach is taken by the following Java implementation.
At the end of each pass, the records are copied back to the original
array.::

   static void radix(Integer[] A, Integer[] B,
                     int k, int r, int[] count) {
     // Count[i] stores number of records in bin[i]
     int i, j, rtok;

     for (i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits
       for (j=0; j<r; j++) count[j] = 0;    // Initialize count

       // Count the number of records for each bin on this pass
       for (j=0; j<A.length; j++) count[(A[j]/rtok)%r]++;

       // count[j] will be index in B for last slot of bin j.
       for (j=1; j<r; j++) count[j] = count[j-1] + count[j];

       // Put records into bins, working from bottom of bin
       // Since bins fill from bottom, j counts downwards
       for (j=A.length-1; j>=0; j--)
         B[--count[(A[j]/rtok)%r]] = A[j];

       for (j=0; j<A.length; j++) A[j] = B[j]; // Copy B back
     }
   }

The first inner ``for`` loop initializes array ``cnt``.
The second loop counts the number of records to be assigned to each
bin.
The third loop sets the values in ``cnt`` to their proper
indices within array ``B``.
Note that the index stored in ``cnt[j]``
is the *last* index for bin ``j``; bins are filled
from high index to low index.
The fourth loop assigns the records to the bins (within
array ``B``).
The final loop simply copies the records back to
array ``A`` to be ready for the next pass.
Variable ``rtoi`` stores :math:`r^i` for use in bin computation
on the :math:`i`'th iteration.
The following visualization illustrates the process.
<commit_msg>Update Radix Sort pseudocode<commit_after>.. This file is part of the OpenDSA eTextbook project. See
.. http://algoviz.org/OpenDSA for more details.
.. Copyright (c) 2012 by the OpenDSA Project Contributors, and
.. distributed under an MIT open source license.

.. avmetadata:: Radix Sort
   :author: <NAME>
   :prerequisites: BinSort
   :topic: Sorting
   :short_name: RadixSort

.. _RadixSort:

.. include:: JSAVheader.rinc

.. index:: ! Radix Sort

Radix Sort
==========

The major problem with Binsort is that it does not work so well for a
large keyrange.
Fortunately, there is a way to keep the number of bins small and the
related processing relatively cheap while using the idea of binning
the records with similar key values.
Consider a sequence of records with keys in the range 0 to 99.
If we have ten bins available, we can first assign records to bins by
taking their key value modulo 10.
Thus, every key will be assigned to the
bin matching its rightmost decimal digit.
We can then take these records from the bins **in order**,
and reassign them to the bins
on the basis of their leftmost (10's place) digit.
We will define values in the range 0 to 9 to have a leftmost digit of
0.
In other words, assign the :math:`i`'th record from array ``A`` to
a bin using the formula ``A[i]/10``.
If we now gather the values from
the bins **in order**, the result is a sorted list.
We can see this process in the following visualization.

.. avembed:: AV/Sorting/radixLinkAV.html
   :showbutton: show
   :title: Linked Radix Sort

In this example, we have :math:`r=10` bins and key values in
the range 0 to :math:`r^2-1`.
The total computation is :math:`\Theta(n)`, because we look at each
record and each bin a constant number of times.
This is a great improvement over the simple Binsort where the number
of bins must be as large as the key range.
Note that the example uses :math:`r = 10` so as
to make the bin computations easy to visualize:
Records were placed into bins based on the value of first the
rightmost and then the leftmost decimal digits.
Any number of bins would have worked.
This is an example of a :dfn:`Radix Sort`, so called because the
bin computations are based on the :dfn:`radix` or the
:dfn:`base` of the key values.
This sorting algorithm can be extended to any number of
keys in any key range.
We simply assign records to bins based on the
keys' digit values working from the rightmost digit to the leftmost.
If there are :math:`k` digits, then this requires that we assign keys to
bins :math:`k` times.

Here is a practice exercise for placing keys into bins.

.. avembed:: Exercises/Sorting/RadixsortPRO.html
   :showbutton: hide
   :title: Radix Sort Practice

As with Mergesort, an efficient implementation of Radix Sort is
somewhat difficult to achieve.
In particular, we would prefer to sort an array of values and avoid
processing linked lists.
If we knew how  many values would be in each bin, then an auxiliary
array of size :math:`r` can be used to define these lengths and guide
us to were each one starts in the output array.
For example, if during the first pass the 0 bin will receive three
records and the 1 bin will receive five records, then we could simply
reserve the first three array positions for the 0 bin and the next
five array positions for the 1 bin.
Exactly this approach is taken by the following Java implementation.
At the end of each pass, the records are copied back to the original
array.::

   static void radix(Integer[] A, Integer[] B,
                     int k, int r, int[] count) {
     // Count[i] stores number of records in bin[i]
     int i, j, rtok;

     for (i=0, rtok=1; i<k; i++, rtok*=r) { // For k digits
       for (j=0; j<r; j++) count[j] = 0;    // Initialize count

       // Count the number of records for each bin on this pass
       for (j=0; j<A.length; j++) count[(A[j]/rtok)%r]++;

       // count[j] will be index in B for last slot of bin j.
       // First, reduce count[0] because indexing starts at 0, not 1
       count[0] = count[0] - 1;
       for (j=1; j<r; j++) count[j] = count[j-1] + count[j];

       // Put records into bins, working from bottom of bin
       // Since bins fill from bottom, j counts downwards
       for (j=A.length-1; j>=0; j--) {
         B[count[(A[j]/rtok)%r]] = A[j];
	 count[(A[j]/rtok)%r] = count[(A[j]/rtok)%r] - 1;
       }
       for (j=0; j<A.length; j++) A[j] = B[j]; // Copy B back
     }
   }

The first inner ``for`` loop initializes array ``cnt``.
The second loop counts the number of records to be assigned to each
bin.
The third loop sets the values in ``cnt`` to their proper
indices within array ``B``.
Note that the index stored in ``cnt[j]``
is the *last* index for bin ``j``; bins are filled
from high index to low index.
The fourth loop assigns the records to the bins (within
array ``B``).
The final loop simply copies the records back to
array ``A`` to be ready for the next pass.
Variable ``rtoi`` stores :math:`r^i` for use in bin computation
on the :math:`i`'th iteration.
The following visualization illustrates the process.

{'fraction_non_alphanumeric': 0.08547692923631268, 'fraction_numerical': 0.008107296566910218, 'mean_word_length': 3.515137821961139, 'pattern_counts': {'":': 0, '<': 15, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '4405511', 'n_tokens_mistral': 3004, 'n_tokens_neox': 2860, 'n_words': 1593}