Close
Register
Close Window

Show Source |    | About   «  17.21. Sorting Part 1   ::   Contents   ::   17.23. Stacks and Queues  »

17.22. Sorting Part 2

17.22.1. Sorting Part 2

17.22.1.1. Shellsort

17.22.1.2. Shellsort (2)

static void shellsort(int[] A) {
  for (int i=A.length/2; i>2; i/=2) { // For each increment
    for (int j=0; j<i; j++) {         // Sort each sublist
      inssort2(A, j, i);
    }
  }
  inssort2(A, 0, 1);     // Could call regular inssort here
}

/** Modified Insertion Sort for varying increments */
static void inssort2(int[] A, int start, int incr) {
  for (int i=start+incr; i<A.length; i+=incr)
    for (int j=i; (j>=incr) && (A[j] < A[j-incr]); j-=incr)
      Swap.swap(A, j, j-incr);
}

17.22.1.3. Mergesort

17.22.1.4. .

.

17.22.1.5. Mergesort cost

  • Mergesort cost:

  • Mergesort is also good for sorting linked lists.

  • Mergesort requires twice the space.

17.22.1.6. Quicksort

static void quicksort(Comparable[] A, int i, int j) { // Quicksort
  int pivotindex = findpivot(A, i, j);  // Pick a pivot
  Swap.swap(A, pivotindex, j);               // Stick pivot at end
  // k will be the first position in the right subarray
  int k = partition(A, i, j-1, A[j]);
  Swap.swap(A, k, j);                        // Put pivot in place
  if ((k-i) > 1) { quicksort(A, i, k-1); }  // Sort left partition
  if ((j-k) > 1) { quicksort(A, k+1, j); }  // Sort right partition
}
static int findpivot(Comparable[] A, int i, int j)
  { return (i+j)/2; }

17.22.1.7. Quicksort Partition

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.8. Quicksort Partition Cost

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.9. Quicksort Summary

17.22.1.10. Quicksort Worst Case

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.11. .

.

17.22.1.12. Quicksort Best Case

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.13. .

.

17.22.1.14. Quicksort Average Case

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.15. Optimizations for Quicksort

  • Better Pivot

  • Inline instead of function calls

  • Eliminate recursion

  • Better algorithm for small sublists: Insertion sort
    • Best: Don’t sort small lists at all, do a final Insertion Sort to clean up.

17.22.1.16. Heapsort

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.17. Heapsort Analysis

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.18. Binsort

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

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.19. Radix Sort: Linked List

17.22.1.20. .

.

17.22.1.21. Radix Sort: Array

17.22.1.22. 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
  }
}

17.22.1.23. .

.

17.22.1.24. Radix Sort Analysis

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

17.22.1.25. 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}\]

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

17.22.1.27. Sorting Lower Bound (2)

Settings

Proficient Saving... Error Saving
Server Error
Resubmit

   «  17.21. Sorting Part 1   ::   Contents   ::   17.23. Stacks and Queues  »

nsf
Close Window