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

6.Shellsort§

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);
}

Mergesort

.

.

Mergesort cost

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

Quicksort Partition

1 / 20 Settings
<<<>>>

When we start the partition function, pivot value 60 has been moved to the right most position.

  1. 760
  2. 61
  3. 572
  4. 883
  5. 854
  6. 425
  7. 836
  8. 737
  9. 488
  10. 609
Proficient Saving... Error Saving
Server Error
Resubmit

Quicksort Partition Cost

1 / 10 Settings
<<<>>>

To analyze Quicksort, we first analyze the findpivot and partition functions when operating on a subarray of length $k$

Proficient Saving... Error Saving
Server Error
Resubmit

Quicksort Summary

Quicksort Worst Case

1 / 8 Settings
<<<>>>

Quicksort's worst case will occur when the pivot does a poor job of breaking the array, that is, when there are no records in one partition, and $n-1$ records in the other

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Quicksort Best Case

1 / 7 Settings
<<<>>>

Quicksort's best case occurs when the selected pivot always breaks the array into two equal halves

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

.

.

Quicksort Average Case

1 / 12 Settings
<<<>>>

QuickSort is a recursive function, accordingly we should end up with a recursive relation to describe its average case running time

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

Optimizations for Quicksort

Heapsort

1 / 51 Settings
<<<>>>

Initially, we start with our unsorted array.

  1. 730
  2. 61
  3. 572
  4. 883
  5. 604
  6. 425
  7. 836
  8. 727
  9. 488
  10. 859
Created with Raphaël 2.1.2
73
6
57
88
60
72
48
85
42
83
Proficient Saving... Error Saving
Server Error
Resubmit

Heapsort Analysis

1 / 12 Settings
<<<>>>

The first step in heapsort is to heapify the array. This will cost $\theta(n)$ running time for an array of size $n$.
Consider the following structure of a Max Heap

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit

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
  1. 90
  2. 81
  3. 42
  4. 63
  5. 54
  6. 35
  7. 76
  8. 17
  9. 28
  10. 09
B
  1. 0
  2. 1
  3. 2
  4. 3
  5. 4
  6. 5
  7. 6
  8. 7
  9. 8
  10. 9
Proficient Saving... Error Saving
Server Error
Resubmit

Radix Sort: Linked List

.

.

Radix Sort: Array

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

.

.

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$

Created with Raphaël 2.1.2
  1. 800
  2. 781
  3. 452
  4. 583
  5. 414
  6. 15
  7. 256
  8. 527
  9. 58
  10. 279
  11. 1310
  12. 8611
$n$
Proficient Saving... Error Saving
Server Error
Resubmit

Empirical Analysis

Sort101001K10K100K1MUpDownInsertion.00023.0070.6664.987381.06744200.04129.05Bubble.00035.0202.25277.9427691.0282068070.64108.69Selection.00039.0120.6972.477356.078000069.7669.58Shell.00034.0080.141.9930.25540.440.79Shell/O.00034.0080.121.9129.05300.360.64Merge.00050.0100.121.6119.32190.830.79Merge/O.00024.0070.101.3117.21970.470.66Quick.00048.0080.111.3715.71620.370.40Quick/O.00031.0060.091.1413.61430.320.36Heap.00050.0110.162.0826.73911.571.56Heap/O.00033.0070.111.6120.83341.011.04Radix/4.00838.0810.797.9979.98087.977.97Radix/8.00799.0440.403.9940.04044.003.99

Sorting Lower Bound (1)

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

Created with Raphaël 2.1.2
Proficient Saving... Error Saving
Server Error
Resubmit