CPS 100, Ramm - Fall 1999 - 10/18/99 #19

Sorting

• O(n log n) sorts are fastest comparison based sorts
  All use a divide and conquer strategy
  • Quick sort is fast, degrades to O(N^2) in the worst case
  • Merge sort is good in worst case, uses extra storage, is stable
  • Binary search tree sort is good if tree is kept balanced
  • Heap sort is good in worst case, no extra storage

• Quicksort

  1. A pivot element of the vector being sorted is chosen. Elements of the vector are rearranged so that elements less than or equal to the pivot are moved before the pivot. Elements greater than the pivot are moved after the pivot. This is called the partition step.

  2. Quick sort (recursively) the elements before the pivot.

  3. Quick sort (recursively) the elements after the pivot.

• The Partition Function

  Desired outcome:

  +-------------------+---+------------------+

  |...elements <= X...| X |...elements > X...|

  +-------------------+---+------------------+

  first...............pivot...............last

  After several iterations:

  +---+------------+-----------+-------------+

  | X |... <= X ...|... > X ...|... ? ? ? ...|

  +---+------------+-----------+-------------+

  first...........p.............k.........last

  All elements processed:

  +---+----------------+---------------------+

  | X |..... <= X .....|........ > X ........|

  +---+----------------+---------------------+

  first...............p...................last

  After swapping 1st element to pivot loc:

  +---+------------+---+---------------------+

  |..... <= X .....| X |........ > X ........|

  +---+------------+---+---------------------+

  first............pivot..................last

  • Note Invariant: 2nd diagram true after every iteration

• Looking at the Code
  timesort.cc
  
  
  

• Analysis of Quick Sort
  • Recurrence Relations
  • Big O

• Pathological Situations (and Solutions)
  • Presorted Data!
    middle element for pivot
  • Repeated Values
    different "sweep"
  • Unlucky
    median of three for pivot
  • Data intentionally engineered to make programmer look bad
    randomization

• Merge Sort
  1. Divide list into two equal halves
  2. Quick sort (recursively) the elements after the pivot.
  3. Merge sorted sublists together
  • Uses extra storage (when using vectors)
  • Can use linked lists (re-link nodes on merging)
  • Problems with linked lists?

  void mergesort(Vector<string> & a, int first, int last)
  {
      if (first < last)
      {
          int middle = (first + last)/2; 
          mergesort(a, first, middle);
          mergesort(a, middle+1, last);
          merge(a, first, middle, last);
      }
  }
  

• What is a merge?
  • Use in external sorting

• Analysis of Merge Sort
  • Recurrence Relations
  • Big O

• Binary Tree Sort (use Binary Search Tree)
  • Seldom used as a direct sorting technique.
    Can be used if binary search tree is used for retrieval and/or frequent update
  • Performance
    • Build Tree O(_______)
    • InOrder Traversal of Tree O(_______)
    • Worst Case O(_______)

• Heap Sort
  • Look at heap details at another time
  • Use functionality
  • Heap has min (for min-heap, max for max-heap) at root
  • Create Heap: O(N)
  • Remove min from Heap (and rebuild): O(log N)
  • To get sorted list:
    • Create Heap
    • Remove min N times
  • Get O(N) + N* O(log N) =>> O(N log N)
  
  
  
  

• Shell Sort
  • Between O(N^1.?) and O(N^2) where ? might be as small as 2
  • Easy to code
  • Sometimes called Diminishing Gap Sort
  • Algorithm
    • Start by setting gap to N/2 (or some smaller number)
    • Logically look at the data list as gap sublists with elements in each sublist gap apart.
    • Do an Insertion sort for each sublist
    • Repeat all of the above for smaller and smaller gaps using gap=1 on the final pass.
    • Empirically, gap = gap/2.2; gives good results for setting gap smaller and smaller.
    • Any sequence of gaps that ends with a gap of 1 results in a sorted list
  • O(N^1.25) for gap shrinking by factor 2.2

  void
  Shellsort(Vector<string> & a, int n) //from Weiss p 271
  {
      int gap, k, j; string tmp;
  
      for (gap = n/2; gap>0; gap = gap==2 ? 1 : int(gap/2.2) )
          for (k = gap; k < n; k++)
          {
              tmp = a[k];
              for (j = k; j>=gap && tmp<a[j-gap]; j -= gap)
                  a[j] = a[j-gap];
              a[j] = tmp;
          }
  }
  	

  
  

• Combining Sorts
  • Don't take N log N sort to bitter end.
  • How does quicksort median of three pivot partition function work with short lists?
  • Switch to simpler N^2 sort
  • Alternative: Quit early; Use insertion sort to clean up
  • Memory model, locality

• Indirect Sorting (Tag Sorts)
  • Corresponds to real world
    • Imagine realtor sorting properties by price
  • Sort vector of pointers to objects
    • key with data
    • key with pointer
  • Final Reordering of Data
    • may not be required! leave it be
    • extra array of objects to reorder?
    • reorder without extra space?
  • (In place swap)

• Representation: use representation of data to avoid comparing
  • Lower bound: O(N log N) for comparison based sorts
  • (Search Analogies)

• Bucket Sort
  • Not comparison based
  • How many buckets?
  • ? O(_____)

  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
  --0--1--2--3--4--5--6--7--8--9-10-11-12-13-14-15-
  

• Radix Sort
  • What if we don't have enough buckets?
  • Digit at a time
  • "Stable" techniques

  23 34 56 25 44 73 42 26 10 16
  
  |  |  |  |  |  |  |  |  |  |  |
  |  |  |  |  |  |  |  |  |  |  |
  |  |  |  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+--+--+--+
  --0--1--2--3--4--5--6--7--8--9-
  
  |  |  |  |  |  |  |  |  |  |  |
  |  |  |  |  |  |  |  |  |  |  |
  |  |  |  |  |  |  |  |  |  |  |
  +--+--+--+--+--+--+--+--+--+--+
  --0--1--2--3--4--5--6--7--8--9-
  

• IBM Card Sorters
  • 12 Bins
  • 2 passes per character

• ? Binary Version