1. Sorting Part 3
1.1. Binsort
for (i=0; i<A.length; i++)
B[A[i]] = A[i];
1.2. Radix Sort: Linked List
1.3. Radix Sort: Array
1.4. Radix Sort Implementation
static void radix(Integer[] A, int k, int r) {
Integer[] B = new Integer[A.length];
int[] count = new int[r]; // Count[i] stores number of records with digit value 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]++; }
// After processing, count[j] will be index in B for first slot of bin j.
int total = A.length;
for (j=r-1; j>=0; j--) { total -= count[j]; count[j] = total; }
// Put records into bins, working from left to right
for (j=0; j<A.length; 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
}
}
1.5. Radix Sort Analysis
1.6. Empirical Analysis
\[\begin{split}\begin{array}{l|rrrrrrrr}
\hline
\textbf{Sort} & \textbf{10}& \textbf{100} & \textbf{1K}&
\textbf{10K} & \textbf{100K}& \textbf{1M}& \textbf{Up} & \textbf{Down}\\
\hline
\textrm{Insertion} & .00023 & .007 & 0.66 & 64.98 & 7381.0 & 674420 & 0.04 & 129.05\\
\textrm{Bubble} & .00035 & .020 & 2.25 & 277.94 & 27691.0 & 2820680 & 70.64 & 108.69\\
\textrm{Selection} & .00039 & .012 & 0.69 & 72.47 & 7356.0 & 780000 & 69.76 & 69.58\\
\textrm{Shell} & .00034 & .008 & 0.14 & 1.99 & 30.2 & 554 & 0.44 & 0.79\\
\textrm{Shell/O} & .00034 & .008 & 0.12 & 1.91 & 29.0 & 530 & 0.36 & 0.64\\
\textrm{Merge} & .00050 & .010 & 0.12 & 1.61 & 19.3 & 219 & 0.83 & 0.79\\
\textrm{Merge/O} & .00024 & .007 & 0.10 & 1.31 & 17.2 & 197 & 0.47 & 0.66\\
\textrm{Quick} & .00048 & .008 & 0.11 & 1.37 & 15.7 & 162 & 0.37 & 0.40\\
\textrm{Quick/O} & .00031 & .006 & 0.09 & 1.14 & 13.6 & 143 & 0.32 & 0.36\\
\textrm{Heap} & .00050 & .011 & 0.16 & 2.08 & 26.7 & 391 & 1.57 & 1.56\\
\textrm{Heap/O} & .00033 & .007 & 0.11 & 1.61 & 20.8 & 334 & 1.01 & 1.04\\
\textrm{Radix/4} & .00838 & .081 & 0.79 & 7.99 & 79.9 & 808 & 7.97 & 7.97\\
\textrm{Radix/8} & .00799 & .044 & 0.40 & 3.99 & 40.0 & 404 & 4.00 & 3.99\\
\hline
\end{array}\end{split}\]
1.7. Sorting Lower Bound (1)
We would like to know a lower bound for the problem of sorting
Sorting is \(O(n \log n)\) (average, worst cases) because we know of algorithms with this upper bound.
Sorting I/O takes \(\Omega(n)\) time. You have to look at all records to tell if the list is sorted.
We will now prove \(\Omega(n log n)\) lower bound for sorting.