Question

The following submission rules apply: • For those questions requiring programs, the solutions must be implemented using JavaScript or Java. o Appropriate self-documenting comments in the source code are mandatory, consistent with good programming practices. o Solutions must be provided in plain text so that formatting is not lost. • All answers must be provided in this document. • Sources must be given accurate and complete citations sufficient for the instructor to find and confirm them.

1 Determine and explain whether RadixSort is a stable sorting algorithm

Answer 1

public class PrimitiveTypesMinMax {
   public static void main(String[] args) {
      // int (32-bit signed integer)
      System.out.println("int(min) = " + Integer.MIN_VALUE);
      System.out.println("int(max) = " + Integer.MAX_VALUE);
      System.out.println("int(bit-length) = " + Integer.SIZE);
      // byte (8-bit signed integer)
      System.out.println("byte(min) = " + Byte.MIN_VALUE);
      System.out.println("byte(max) = " + Byte.MAX_VALUE);
      System.out.println("byte(bit-length)=" + Byte.SIZE); 
      // short (16-bit signed integer)
      System.out.println("short(min) = " + Short.MIN_VALUE);
      System.out.println("short(max) = " + Short.MAX_VALUE);
      System.out.println("short(bit-length) = " + Short.SIZE);
      // long (64-bit signed integer)
      System.out.println("long(min) = " + Long.MIN_VALUE); 
      System.out.println("long(max) = " + Long.MAX_VALUE);
      System.out.println("long(bit-length) = " + Long.SIZE);
      // char (16-bit character or 16-bit unsigned integer)
      System.out.println("char(min) = " + (int)Character.MIN_VALUE);
      System.out.println("char(max) = " + (int)Character.MAX_VALUE);
      System.out.println("char(bit-length) = " + Character.SIZE);
      // float (32-bit floating-point)
      System.out.println("float(min) = " + Float.MIN_VALUE);
      System.out.println("float(max) = " + Float.MAX_VALUE);
      System.out.println("float(bit-length) = " + Float.SIZE);
      // double (64-bit floating-point)
      System.out.println("double(min) = " + Double.MIN_VALUE);
      System.out.println("double(max) = " + Double.MAX_VALUE);
      System.out.println("double(bit-length) = " + Double.SIZE);
   }
}

radix sort(L):
    {
    bucket sort by a
    bucket sort by b
    bucket sort by c
    ...
    }

or more simply

    radix sort(L):
    {
    while (some key is nonzero)
    {
        bucket sort(keys mod 10)
        keys = keys / 10
    }
    }

The only possibly strange part: Why do we do the sort least important digit first? For that matter, why do we do more than one bucket sort, since the last one is the one that puts everything into place?

Answer: If we're trying to sort things by hand we tend to do something different: first do a bucket sort, then recursively sort the values sharing a common first digit. This works, but is less efficient since it splits the problem up into many subproblems. By contrast, radix sorting never splits up the list; it just applies bucket sorting several times to the same list.

In radix sorting, the last pass of bucket sorting is the one with the most effect on the overall order. So we want it to be the one using the most important digits. The previous bucket sorting passes are used only to take care of the case in which two items have the same key (mod 10) on the last pass.

Correctness:

We prove that the algorithm is correct by induction. The induction hypothesis is that after i steps, the numbers are sorted by key modulo 10^i. Certainly after no steps, all numbers are the same modulo 1, and are therefore sorted by that value, so the base case is true. Inductively, step i+1 sorts by key / 10^i. If two numbers have the same value of key/10^i, the stability property of bucket sorting leaves them sorted by lower order digits; and if they don't have the same value, the bucket sort on step i+1 puts them in the right order, so in either case the induction hypothesis holds. For i sufficiently large, taking the keys mod 10^i doesn't change them, at which point the list is sorted.

Analysis:

The algorithm takes O(n) time per bucket sort.
There are log_10 k = O(log n) bucket sorts.
So the total time is O(n log k).