Archive | math595tta

RSS feed for this section

quick sort

  • Intro: sorting; bubble sort
  • Lower bound: information based
    \[
    \log{n!}\approx n\log{n}.
    \]
  • Idea: divide and conquer (Hoare).
  • Quicksort and partition.
  • Average case analysis. Address the number of comparisons
  • Connection to binary search trees.
  • Expected number of comparisons: fundamental recursion
    \[
Read full story Comments { 0 }