Loading [MathJax]/jax/output/HTML-CSS/jax.js

DSA Coursenotes

Chapter 7 Week 8

Show Source | | About « 6.3. Sorting: Faster Sorts :: Contents :: 7.2. Disk Drives »

7.1. Sorting: Limits to Sorting¶

7.1.1. Limits to Sorting¶

7.1.1.1. Binsort¶

  for (i=0; i<A.length; i++) {
    B[A[i]] = A[i];
  }
1 / 12 Settings
<<<>>>

Here we see a simple Binsort on a permutation of the values 0 to n-1. Move each value A[i] to position B[A[i]].

A
30
61
82
23
54
75
06
17
98
49
B
0
1
2
3
4
5
6
7
8
9

Saving...
Server Error
Resubmit

7.1.1.2. Radix Sort: Linked List¶

Your browser does not support iframes.

7.1.1.3. .¶

.

7.1.1.4. Radix Sort: Array¶

Your browser does not support iframes.

7.1.1.5. 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]++; }

    // 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
  }
}

7.1.1.6. Radix Sort Analysis¶

1 / 11 Settings
<<<>>>

Radixsort starts with an input array of $n$ keys with $k$ digits. Here we have $n=12$ and $k=2$

static void radix(Integer[] A, int k, int r) {
Integer[] B = new Integer[A.length];
int[] count = new int[r];
int i, j, rtok;
for (i=0, rtok=1; i<k; i++, rtok*=r) {
for (j=0; j<r; j++)
count[j] = 0;
for (j=0; j<A.length; j++)
count[(A[j]/rtok)%r]++;
count[0] = count[0] - 1;
for (j=1; j<r; j++)
count[j] = count[j-1] + count[j];
for (j=A.length-1; j>=0; j--) {
B[count[(A[j]/rtok)%r]] = A[j];
count[(A[j]/rtok)%r]--;
}
for (j=0; j<A.length; j++) A[j] = B[j];
}
}
30
481
452
653
254
285
36
917
348
299
2610
1411
$n$
00
01
02
03
04
05
06
07
08
09
$r$
910
31
32
343
144
455
656
257
268
489
2810
2911
$n$

Saving...
Server Error
Resubmit

7.1.1.7. 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}$

7.1.1.8. 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.

7.1.1.9. Sorting Lower Bound (2)¶

1 / 24 Settings
<<<>>>

We will illustrate the Sorting Lower bound proof by showing the decision tree that models the processing of InsertionSort on an array of 3 elements XYZ

XYZ
XYZ YZX
XZY ZXY
YXZ ZYX
$Y < X?$
Yes
YXZ
YXZ
YZX
ZYX
No
XYZ
XYZ
XZY
ZXY
$Z < X?$
Yes
YZX
YZX
ZYX
No
YXZ
$Z < Y?$
Yes
No
ZYX
YZX
$Z < Y?$
Yes
XZY
XZY
ZXY
No
XYZ
$Z < X?$
Yes
No
ZYX
YZX

Saving...
Server Error
Resubmit

Contact Us || Privacy | | License « 6.3. Sorting: Faster Sorts :: Contents :: 7.2. Disk Drives »