Shared Flashcard Set

Details

COP4531 Midterm
Containers, Gen Algorithm, Gen Set, Gen Sort
73
Computer Science
Undergraduate 4
10/05/2009

Additional Computer Science Flashcards

 


 

Cards

Term
Generic Container
Definition
a generic container is a template class C desinged to store elements of an arbitrary proper type that is specified as a template argument.
Term
Positional Container
Definition
a generic container that is organized by position which means the client may insert any T object at any position in c, client may remove T object at any [position in c and at least one push/pop/retrieve triple
Term
Sequential Container
Definition
is a positional container c such that c is a positional container, organized sequentially, typically access to front and back elements, some push/pop pair supported fron or back
Term
Container Taxonomy Hierarchy (partial)
Definition
  • Positional
    • Sequential
      • vector
      • list
      • deque
    • Other
      • binary tree
      • graph
  • Associative
    • Unordered
      • hash set
      • hash map
    • Ordered
      • priority queue
      • set
      • map
      • multiset
      • multimap
  • Term
    Sequential Container Interface
    Definition
  • Required
    • Proper Type
    • Empty(), Size()
    • Clear()
    • Forward Iterators
    • Iterator Support: Begin(), End()
  • Optional
    • Front(), PushFront(t), PopFront()
    • Back(), PushBack(t), PopBack()
    • Insert(I,t), Remove(I)
    • Bidirectional or Random Access Iterators
    • Iterator Support: rBegin(), rEnd()
  • Term
    Runtime Constraints
    Definition

    Runtime complexity <= O(1) (possibly amortized)

    • Empty()
    • Begin(), End()
    • Front(), PushFront(t), PopFront()
    • Back(), PushBack(t), PopBack()
    • Insert(I,t), Remove(I)
    • All Iterator operations

    Runtime complexity <= O(n), n = no of elements stored

    • Clear()

    • Size()
    • Constructors and Destructor
    • Assignment
    Term
    Forward Iterator Interface
    Definition

    Proper type

    Operations

    int       operator == (const Iterator& I2);
    int       operator != (const Iterator& I2);
    Iterator& operator = (const Iterator&);
    const T&  operator *() const;
    T&        operator *();
    Iterator& operator ++();
    Iterator  operator ++(int);
    
    Term

    Bidirectional Iterator Interface

     

    Definition

    Proper Type

    Forward Iterator

    Additional Operations

    Iterator& operator --();
    Iterator  operator --(int);
    
    Term
    Random Access Iterator
    Definition
    Bidirectional Iterator plus
    T&        operator [] (size_t i);
    const T&  operator [] (size_t i) const;
    "pointer" arithmetic
    
    Term

    FSU sContainers

    TVector, TList, TDeque

    What do they all have in common?

    Definition
  • All:
    • Proper Type
    • Front(), Back()
    • PushBack(t), PopBack()
    • Clear()
    • Empty(), Size()
    • Bidirectional Iterators
    • Begin(), End(), rBegin(), rEnd()
  • Term

    FSU sContainers

    TVector, TList, TDeque

    What are the sContainer options that conform to runtime constraints:

    Definition
  • TVector: SetSize(n), SetCapacity(n), 2-parameter constructor, bracket operator, random access iterators
  • TList: PushFront(t), PopFront(), Insert(I,t), Remove(I), Remove(t)
  • TDeque: PushFront(t), PopFront(), bracket operator, random access iterators
  • Term
    Vector Interface
    Definition

    The interface for fsu::TVector conforms to the constraints for sequential containers. The operations that distinguish TVector among all sContainers are highlighted in color.

    Size() returns the number of elements in the vector, and Capacity() returns the number of elements of storage that is currently owned by the vector: the size of the "footprint".

    SetCapacity(n) always establishes a footprint of exactly n elements. SetSize(n,t) expands the capacity if necessary to achieve size n, but never shrinks the capacity; new elements are initialized to t.

    Term
    Vector Implementation Plan
    Definition

    The plan shows that we are just putting a nice "face" on a C-array, managing memory for the client program. The client can manage the footprint in as much detail as desired via the "allocator" methods SetSize and SetCapacity. Note that SetSize is expansive only, whereas SetCapacity sets the footprint size precisely, whether increasing or decreasing from the current capacity.

    Term
    Vector Iterator Interface: Random Access Iterator
    Definition
    The operators in this interface are those of a random access iterator. The methods Retrieve() are depracated, serving the same functionality as operator*.
    Term
    Vector Iterator Implementation Plan
    Definition

    The implementation plan for fsu::TVector::Iterator is to put a new interface on a raw pointer into the data array. Note that this is the classic unsafe & fast way to implement iterators. The classic safe & slow way is taken in fsu::TDeque::Iterator

    Term
    List Interface
    Definition

    The interface for fsu::TList conforms to the constraints for sequential containers. The operations that distinguish TList among all sContainers are highlighted in color.

    Term
    List Implementation Plan
    Definition

    The new idea facilitating the list is that of the dynamic link: with every data element, also store the address of the next data element and the previous data element. This way, elements of a list can be scattered anywhere in memory, so long as the link information is stored with the elements.

    Term
    List Iterator Implementation Plan
    Definition

    A list iterator needs to access an element of the list directly. The simplest way to do this is via the links in the list. The implementation plan is to provide a protected pointer to a current link that is accessed by the public methods and operators:

      template <typename T>
      class listiterator
      {
        protected:
          link * currLink;  // pointer to current link in a list
      
        public:
          listiterator& operator ++();
          // ... 
      } ;
      

    By keeping the link pointers protected (in both list and list iterator), we are preventing a client from accessing the list structure, while providing access to the list data.

    Maintaining the integrity of list structure while implementing all of the list and list iterator methods is fairly complicated and error-prone programming. Once implemented, however, the resulting generic list and iterator classes are extremely useful and at the same time extremely robust and client-friendly.

    Term
    Deque Implementation Plan
    Definition

    Our implementation for TDeque uses another item from classical data structures tradition: the circular array. (The STL version of deque uses a different implementation.) The essential ingredients are depicted in the slide. Here is the actual declaration of protected data from the TDeque class definition:

    protected:
      T*           content;
      unsigned int content_size, beg, end;
    

    Consistency between content and content_size must be maintained at all times: content_size is the size of memory allocated to the array content.

    Term

    Algorithm Components

    Required  & Optional

    Definition

    Required

    Assumptions

    Asserted Outcomes

    Body

    Proof

    Optional

    Execution Speed & Space Performance

    Term
    Sequential Search
    Definition
  • Algorithm for finding a specified value in a collection of values
  • Requires ability to iterate through the collection
  • Pedestrian (literally): walk through the collection, testing at each step
  • Term
    Sequential Search Algorithm
    Definition
    • Assumptions:
      • collection L of data of type T
      • can iterate through L ("begin", "next", "end")
    • Outcomes:
      • decide whether t is in L
      • return boolean (yes/no)
    • Proof: (postponed)
    • Body (written in pseudocode):
      T item = begin(L);
      while (item is in L)
      {
        if (t == item)
          return true;
        item = next(L);
      }
      return false;
      
    Term
    Binary Search
    Definition
    • Algorithm for finding a value in a collection of values
    • Collection must have "array-like" structure
      • random access to data through bracket operator
      • example containers: array, vector, deque
    • Collection must be sorted
      • elements in increasing (or decreasing) order
    • Idea: "Divide and Conquer"
    • Efficiency:
      • very fast
      • no extra space required
    Term
    Binary Search Algorithm
    Definition
    • Three versions:
      • binary_search
      • lower_bound
      • upper_bound
    • Assumptions:
      • collection v of data of type T and size sz
      • v is sorted (increasing order)
      • bracket operator provides random access to elements of v
      • element t of type T
    • Outcomes:
      • binary_search: return true if t is in v, false if not
      • lower_bound: return smallest index i such that t <= v[i]
      • upper_bound: return smallest index i such that t < v[i]
    Term

    lower_ bound

    Binary Search Code

    Definition
    unsigned int lower_bound (T* v, unsigned int size, T t)
    {
      unsigned int   low  = 0;
      unsigned int   mid;
      unsigned int   hih = size;
      while (low < hih)
      {
        mid =  (low + hih) / 2;  
        if (v[mid] < t)          
          low = mid + 1;         
        else                     
          hih = mid;             
      }  
      return low;
    }
    
    Term

    upper_bound

    Binary Search

    Definition
    unsigned int upper_bound (T* v, unsigned int size, T t)
    {
      unsigned long   low = 0;
      unsigned long   mid;
      unsigned long   hih = size;
      while (low < hih)
      {
        mid =  (low + hih) / 2;
        if (t < v[mid]))
          hih = mid;                
        else                        
          low = mid + 1;            
      }  
      return low;
    }
    
    Term

    binary_search

    Algorithm

    Definition
    bool binary_search (T* v, unsigned int size, T t)
    {
      unsigned int lb = lower_bound(v,t);
      if (lb < size)
      {
        if (t == v[lb])
        {
          return true;
        }
      }
      return false;
    }
    
    Term
    Correctness and Loop Invariants
    Definition
    • Loops
      • Loop termination
      • State entering loop
      • State exiting loop
    • Loop invariants
      • Statements that are true in each iteration of loop
      • Analogous to the "induction" part of mathematical induction
    Term
    Loop Invariants - Sequential Search
    Definition
    boolean sequential_search
    {
      T item = first(L);
      // Before entering loop: t has not been found
      while (item is in L)
      {
        // loop invariant: current item has not been tested
        if (t == item)
          return true;
        // loop invariant: t is not current item
        item = next(L);
      }
      return false;
    }
    
    Term
    Loop Invariants - Binary Search
    Definition
    unsigned int lower_bound (T* v, unsigned int max, T t)
    {
      unsigned int   low  = 0;
      unsigned int   mid;
      unsigned int   hih = max;
      while (low < hih)
      {
        // (1) low < hih
        // (2) v[low - 1] < t (if index is valid)
        // (3) t <= v[hih]     (if index is valid)
        mid =  (low + hih) / 2;  
        if (v[mid] < t)          
          low = mid + 1;         
        else                     
          hih = mid;             
        // (4) low <= hih
        // (5) hih - low has decreased
        // (6) v[low - 1] < t (if index is valid)
        // (7) t <= v[hih]     (if index is valid)
      }  
      return low;
    }
    
    Term
    Computational Complexity
    Definition
  • Compares growth of two functions
    • function domains include (most) positive integers
    • function values are non-negative real numbers
  • Independent of
    • (any finite number of) initial values
    • constant multipliers
    • "lower order" effects
  • "Big O" Notation
  • "Big Omega" Notation
  • "Big Theta" Notation
  • Term
    Big O
    Definition

    g(n) <= O(f(n)) iff there exist positive constants c and n0 such that 0 <= g(n) <= cf(n) for all n >= n0
    "g is asymptotically bounded above by f "

    Term
    Big Omega
    Definition

    g(n) >= Ω(f(n)) iff there exist positive constants c and n0 such that 0 <= cf(n) <= g(n) for all n >= n0
    "g is asymptotically bounded below by f "

    Term
    Big Theta
    Definition

    g(n) = Θ(f(n)) iff there exist positive constants c1, c2, and n0 such that 0 <= c1f(n) <= g(n) <= c2(n) for all n >= n0
    "g is asymptotically bounded above and below by f "

    Term
    Algorithm Complexity
    Definition

    Stated in terms of Big O, Big Omega, or Big Theta

    Independent of hardware

    Independent of programming language

    Steps:

    1. n = some measure of size of input to the algorithm
    2. find an atomic notion of computational activity to count
    3. find f(n) = the number of atomic activities done by the algorithm for input of size n
    4. complexity of algorithm <= O(f(n)) (or >= Ω(f(n)) or = Θ(f(n)))

    Term
    Algoritm Complexity - LOOPS
    Definition
    for (i = 0; i < n; ++i)
    {
      // 3 atomics in loop body
    }
    
  • Complexity = Θ(3n) = Θ(n)
  • Term
    Algorithm Complexity - Loops with Break
    Definition
    for (i = 0; i < n; ++i)
    {
      // 3 atomics in loop body
      if (condition) break;
    }
    
  • Complexity <= O(n)
  • Term
    Algorithm Complexity - Loops in Sequence
    Definition
      for (i = 0; i < n; ++i)
      {
        // 3 atomics in loop body
      }
      for (i = 0; i < n; ++i)
      {
        // 5 atomics in loop body
      }
      
    • Complexity <= O(3n + 5n) <= O(n)
    Term
    Algorithm Complexity - Loops Nested
    Definition
    for (i = 0; i < n; ++i)
    {
      // 2 atomics in outer loop body
      for (j = 0; j < n; ++j)
      {
        // 3 atomics in inner loop body
      }
    }
    
  • Complexity <= O((2 + 3n)n) <= O(2n + 3n2) <= O(n2)
  • Complexity = Θ((2 + 3n)n) = Θ(2n + 3n2) = Θ(n2)
  • Term
    Algorithm Complexity Sequential Search Simplified
    Definition
      T    item  = first(L);
      bool found = false;
      while (item is in L)
      {
        if (t == item)
          found = true;
        item = next(L);
      }
      return found;
      
    • simplified sequential search (no early break from loop)
    • notion of input size: n = size of container
    • atomic computation: comparison (call to operator ==())
    • f(n) = (1 compare in loop body) x (iterations of loop body)
         = (1) x (n)
         = Θ(n)
    • algorithm complexity = Θ(n)
    Term
    Algorithm Complexity - Sequential Search
    Definition
      T    item  = first(L);
      while (item is in L)
      {
        if (t == item)
          return true;
        item = next(L);
      }
      return false;
      
    • sequential search with early loop break
    • notion of input size: n = size of container
    • atomic computation: comparison (call to operator ==())
    • f(n) = (1 compare in loop body) x (iterations of loop body)
          <= (1) x (n)
          = Θ(n)
    • algorithm complexity <= O(n)
    Term

    Algorithm Complexity - Binary Search

    Definition
      lower_bound
      {
        unsigned int   low  = 0;
        unsigned int   mid;
        unsigned int   hih = size;
        while (low < hih)
        {
          mid =  (low + hih) / 2;  
          if (v[mid] < t)          
            low = mid + 1;         
          else                     
            hih = mid;             
        }  
        return low;
      }
      
    • notion of input size: n = size of container
    • atomic computation: comparison
      (call to operator <())
    • f(n) = (1 compare) x (no. of iterations of loop body)
         = (1) x (log n)
         = Θ(log n)
    • algorithm complexity = Θ(log n)
    Term
    Trace the stack of a stack-controlled DFS of a tree.
    Definition

    stack ->
    ---------
    1
    1 2
    1 2 5
    1 2 5 6
    1 2 5 6 8
    1 2 5 6
    1 2 5
    1 2
    1
    1 3
    1 3 9
    1 3 9 7
    1 3 9
    1 3 9 12
    1 3 9 12 10
    1 3 9 12 10 11

    Term
    Trace the queue of a queue-controlled BFS of a tree.
    Definition

    <- queue
    ---------
    1
    2 3 4
    3 4 5 6
    4 5 6 9 10
    5 6 9 10
    6 9 10
    9 10 8
    10 8 7 12
    8 7 12 11
    7 12 11
    12 11
    11

    Term
    Trace quick sort on a vector.
    Definition

    Analysis of Quicksort
    The partition routine is called at most one time for each element
    All comparisons are done inside the partition routine
    Therefore algorithm runtime is O(n + x), where x is the total number
    of comparisons made by the partition routine
    Worst case: x = T(n2)
    Average case: E[x] <= O(n log n)

    Term

    Theory of comparison sorts: runtime lower bound, proof
    Key Comparison Sorts Theorem.

    Definition

    Any comparison sort requires O(n log n) comparisons in the worst case.
    Proof - Use decision tree for the algorithm
    Binary tree with node for each comparison, leaf for each solution
    Each leaf represents a permutation of the input range
    Sort of a particular data set is represented by a descending path to a leaf
    Length of this path = number of comparisons made by the sort
    n! leaves
    Depth >= log2 n!
    log2 n! >= O(n log n) by Stirlings formula

    Term
    Properties of sorts (type[comparison or not], stability, runtime, runspace, assumptions (range specs,
    Definition


    Sort             Runtime  Runspace  Stability  Generic
    Insertion Sort   O(n2)   in place  yes   Bidirectional
    Selection Sort   T(n2)   in place  no   Forward
    Heapsort   T(n log n)  in place  no   Random Access
    Merge Sort   T(n log n) + T(n)   yes   Random Access
    Quicksort   WC = T(n2)
       AC = T(n log n) + T(n)   maybe  Smart Bidirectional
    Counting Sort   T(n + k) + T(k)   yes   function object argument
    Radix Sort   T(d(n + k)) + T(k)   yes   ??
    Bit Sort   T(n) + T(n)    yes  Use funObj in counting sort

     

    n = size of range to be sorted
    k = upper bound of size of integers to be sorted
    d = loop length in radix sort
    Estimates are worst case unless noted otherwiseiterator category, value type)

    Term
    Algorithm Complexities
    Definition

    Algorithm Complexity
    Loops  T(3n) = T(n)
    Loops w/break <= O(n)
    Loops in Seq <= O(3n + 5n) <= O(n)
    Loops nested <= O((2 + 3n)n) <= O(2n + 3n2) <= O(n2)
    Loops nested = T((2 + 3n)n) = T(2n + 3n2) = T(n2)
    Sequen Search = T(n)  Simplified
    Sequen Search <= O(n)
    Binary Search = T(log n)

    Term
    TVector Operation     Runtime Complexity
    Definition

    Requirement      Actual
    PopBack(), Clear()
    Front(), Back()
    Empty(), Size(), Capacity()
    bracket operator []      O(1)     T(1) 
    PushBack(t)       Amortized O(1)     Amortized T(1) 
    SetSize(n), SetCapacity(n)      O(n)     O(n) 
    assignment operator =      O(n), n = Capacity()     T(n), n = Capacity() 
    Constructors, Destructor
    O(n), n = Capacity()      T(n), n = Capacity() 
    Display(os,ofc)            T(n), n = Size() 
    Dump(os)             T(n), n = Capacity() 

    Term
    Trace a traversal of a binary tree [4 kinds]
    Definition

    Traversal  Type Container Visit Vertex
    Inorder     DFS 
    Preorder    DFS Stack  Arrival
    Postorder  DFS Stack  Departure
    Levelorder BFS Queue  Departure

    Term
    Quick Sort
    Definition

    template< class I >
      void g_quick_sort(I p, I r)  // got assistance
      {
       if (r - p > 1)
       {
          I q = PartitionA(p,r);
          g_quick_sort(p,q);
          g_quick_sort(q+1,r);
        }
      }
    template< class I >  // got assistance
      I PartitionA(I p, I r)  
      {
       
     I i = p;
      --r;
      
       for (I j = p; j != r; ++j)
       {
        if ( *j <= *r )
        {
          Swap(*i , *j);     
          ++i;
        }
       }
       // the last place requires no test:
       Swap(*i, *r);
       return i;
      }

    Term
    Merge
    Definition

    // merge
      template < class I, class T >
      void merge(I p, I q, I r)
      {
        T B;                            // temp space for merged copy of A
        g_set_merge(p, q, q, r, B);     // merge the two parts of A to B
        g_copy(B.Begin(), B.End(), p ); // copy B back to A[p,r)
      }

      template < class I > 
      void g_merge_sort(I p,I r)
      {
         size_t size(r - p);
      if(size<2) return;
        
       I q = p + size/2;       // integer arithmetic
          g_merge_sort(p , q);    // recursive call
          g_merge_sort(q,  r);    // recursive call
          fsu::merge( p, q, r );  // defined below
       
      }

    Term
    Selection Sort
    Definition

    selection
     template < class ForwardIterator , class Comparator >
      void g_selection_sort (ForwardIterator beg, ForwardIterator end, Comparator cmp)
      {
        ForwardIterator i, j, k;
        for (i = beg; i != end; ++i)
        {
          k = i;
          for (j = i; j != end; ++j)
            if (cmp(*j , *k))
              k = j;
          Swap (*i, *k);
        }
      }

    Term
    Heap Sort
    Definition


    heap
    template <class I, class P>
      void g_heap_sort (I beg, I end, const P& LessThan)
      // Implements heapsort for the iterators
      // Heapsort has the following attributes:
      //   * fast:     runtime O(size*log(size))
      //   * in-place: the sort happens in the space implied by the iterators
      //   * NOT stable -- the original order of objects a, b may change when
      //                   a == b
      // pre:  I is a random access iterator class (operator [] and "pointer" arithmetic)
      //       T is the value_type of I
      //       P is a predicate class for type T
      // post: the range of values specified by the iterators is ordered by LessThan,
      //       i.e., true = LessThan(a,b)  <==>  a comes before b in the container
      {
        if (end - beg <= 1)
          return;
        size_t size = end - beg;
        size_t i;
        // push elements onto heap one at a time
        for (i = 1; i < size; ++i)
        {
          g_push_heap(beg, beg + (i + 1), LessThan);
        }
      
        // keep popping largest remaining element to end of remaining array
        for (i = size; i > 1; --i)
        {
          g_pop_heap(beg, beg + i, LessThan);
     // XC(beg[0],beg[i-1]) and restructure beg[0..i-2] as POT
        }
      } // end g_heap_sort()

    Term
    what does size mean
    Definition
    When "size" is used it always means a count of the number of items in input
     - it does not mean "sizeof" any type.
    Term
    BinaryTree Iterator properties such as runtime of operations
    Definition

    Runtime Complexity of Iterator Operations
    Theorem. Assume that bt is a binary tree of type TBinaryTree<T> and
    i is an iterator of type
    TBinaryTreePreorderIterator<T>, TBinaryTreeInorderIterator<T>,
    TBinaryTreePostorderIterator<T>, or
    TBinaryTreeLevelorderIterator<T>.
    Then the loop
    for (i = bt.Begin(); i != bt.End(); ++i){}

    has runtime complexity T(bt.Size()).
    Corollary. For any of the four iterator types, operator ++() has amortized runtime complexity T(1).

    Lemma 1. For the cases of preorder, inorder, and postorder,
      the loop in the Theorem makes exactly 2*size edge steps.

    Lemma 2. For the case of levelorder, the loop in the
      Theorem invokes no more than 3*size queue push/pop operations.

    Term
    Push Heap Algorithm
    Definition
  • Add new data at next leaf
  • Repair upward
  • Repeat
    • locate parent
    • if POT not satisfied
    •   swap
    • else
    •   stop
  • Until POT
  • Term
    Pop Heap Algorithm
    Definition
  • Copy last leaf to root  
  • Remove last leaf
  • Repair downward
  • Repeat
    • identify children
    • find larger child
    • if POT not satisfied
    •   swap
    • else
    •   stop
  • Until POT
  • Term
    Generic Heap Algorithms
    Definition
    • Apply to ranges
    • Omit size change (step 1)
    • Specified by random access iterators
    • Currently support:
      • arrays
      • TVector<T>
      • TDeque<T>
    • Source code file: gheap.h
    • Test code file: fgss.cpp
    Term
    Generic XC
    Definition
    template <class T>
    void g_XC (T& t1, T& t2)
    {
      T temp(t1);
      t1 = t2;
      t2 = temp;
    }
    
    Term
    Priority Queue
    Definition
  • Element type with priority
    • typename T t
    • predicate class P p
  • Associative queue operations
    • void Push(t)
    • void Pop()
    • T& Front()
  • Associative property
    • Priority value determined by p
    • Push(t) inserts t (no position implied), increases size by 1
    • Pop() removes element with highest priority value, decreases size by 1
    • Front() returns element with highest priority value, no state change
  • Term
    preorder
    Definition

    void preorder (TNode<T>* root, void (TNode<T>*) visit)
    {
      if (root == 0)
        return;
      visit(root);                   // visit node before visits to children
      preorder(root->lchild, visit); // recursive call
      preorder(root->rchild, visit); // recursive call
    }

    Term
    TBinaryTreeInorderIterator
    Definition
    template < typename T >
    void TBinaryTreeInorderIterator<T>::Initialize (const TBinaryTree<T>& b)
    {
      // enter tree at root
      nav_ = b.Root();
      // slide to leftmost node
      while (nav_.HasLeftChild())
        ++nav_;
    }
    
    Term
    Sort by Insertion
    Definition
    // C c = input container
    sorted_list<T> L;
    C::Iterator i;
    for (i = c.Begin(); i != c.End(); ++i)
      L.Insert(*i);
    // now L is a sorted list of all elements of c
    sorted_list<T>::Iterator j;
    for (i = c.Begin(), j = L.Begin(); j != L.End(); ++i, ++j)
      *i = *j;
    // now c is sorted
    
  • worst case run time = 1 + 2 + ... + n = Θ(n2)
  • replace sorted_list with faster associative container, WCRT = Θ(n log n)
  • not in place
  • Term
    Selection Sort
    Definition
      template < class ForwardIterator >
      void g_selection_sort (ForwardIterator beg, ForwardIterator end)
      {
        ForwardIterator i, j, k;
        for (i = beg; i != end; ++i)
        {
          k = i;
          for (j = i; j != end; ++j)
            if (*j < *k)
              k = j;
          swap (*i, *k);
        }
      }
      
    • in place
    • not stable
    • run time = Θ(n2)
    • requires forward iterators
    Term
    Heap Sort
    Definition
    template <class RAIter>
    void g_heap_sort (RAIter beg, RAIter end)
    {
      if (end - beg <= 1)
        return;
      size_t size = end - beg, k;
    
      // push elements onto heap one at a time
      for (k = 0; k < size; ++k)
        g_push_heap(beg, beg + (k + 1));
       
      // keep popping largest remaining element to end of remaining range
      for (k = size; k > 1; --k)
        g_pop_heap(beg, beg + k);
    }
    
  • in place
  • not stable
  • run time = Θ(n log n)
  • requires random access iterators
  • Term

    Classic Quicksort

    Definition
    void quick_sort(A,p,r)
    {
      if (r - p > 1)
      {
        q = Partition(A,p,r);
        quick_sort(A,p,q);
        quick_sort(A,q+1,r);
      }
    }
    
      size_t Partition(A,p,r)
      {
        i = p;
        for (j = p; j < r-1; ++j)
        {
          if (A[j] <= A[r-1])
          {
            swap(A[i],A[j]);      
            ++i;
          }
        }
        // the last place requires no test:
        swap(A[i],A[r-1]);
        return i;
      }
      
    • Worst Case Run Time = Θ(n2)
    • Average Case Run Time = Θ(n log n)
    Term
    Key Comparisons Sort
    Definition

    Theorem. Any comparison sort requires Ω(n log n) comparisons in the worst case.

    Proof.

    • Use decision tree for the algorithm
    • Binary tree with node for each comparison, leaf for each solution
    • Each leaf represents a permutation of the input range
    • Sort of a particular data set is represented by a descending path to a leaf
    • Length of this path = number of comparisons made by the sort
    • n! leaves
    • Depth >= log2 n!
    • log2 n! >= Ω(n log n) by Stirlings formula
    Supporting users have an ad free experience!