Lecture Notes for SE 598, Data Structures and Algorithms

14 June 2000, Vector Algorithms

1. vector structure

   1. linear structure

      1. one value after another

      2. iterative - for i = 0 to size(v) - 1

   2. recursive structure

      1. a value followed by a vector

      2. recursive - v[0]; f(v[1..size(v) - 1])

   3. often little difference between recursive and linear points of view

      1. conceptually, recursion has more structure than iteration

      2. in implementation, linear code (that is, loops) tends to execute more efficiently than recursive code - but there's usually an easy translation from (tail) recursion to iteration

2. finding a value in a vector - given a vector v and a value x, find x in v or indicate x is not in v

   1. linearly

      1. if v[0] equals x return 0
         if v[1] equals x return 1
         if v[n - 1] equals x return n - 1
         return -1

      2. template <class RandomIterator, typename T>
         static RandomIterator lfind(
           RandomIterator start, RandomIterator end, const T & x) {
         
           while ((start < end) && (*start == x))
             start++;
         
           return start;
           }
         

   2. recursively

      1. if the vector is empty, you won't find x
         if the first element of the vector equals x, you've found it
         look for x in the rest of the vector

      2. template <class RandomIterator, typename T>
         static RandomIterator rfind(RandomIterator start, RandomIterator end, const T & x) {
         
           if (start >= end) return end;
           if (*start == x) return start;
         
           return rfind(start + 1, end, x);
           }
         

3. sorting values in an array - given vector v, permute v so that if i < j, then v[i] < v[j]

   1. linearly

      1. look through the array for the largest element, dragging it along
         look through the array for the next largest element, dragging it along
         ...
         

      2. template <typename RandomIterator>
         static void bubble(RandomIterator start, RandomIterator end) {
           while (start < end) {
             for (RandomIterator s = start + 1; s < end; s++)
               if (*(s - 1) > *s) 
         	swap(*(s - 1), *s);
             end--;
             }
           }
         

   2. recursively

      1. the empty vector is sorted
         suppose the vector v[1..n-1] is sorted; where does v[0] go?

      2. template <typename T>
         static void insert(T * start, T * end) {
         
           if (start < end) {
             insert(start + 1, end);
         
             const T t = *start;
             T * s = start;
             while ((s < end - 1) && (*(s + 1) < t)) {
               *s = *(s + 1);
               s++;
               }
             *s = t;
             }
           }
         

4. indirection

   1. there is no problem that can't be solved with enough levels of indirection

   2. problem - add values to a vector and preserve their order, but quickly determine whether a value is in the vector

   3. sorting and a binary chop finds values in a vector quickly, but sorting messes up the values' order

   4. solution - sort a vector of indices into the value vector; if i < j then values[indices[i]] < values[indices[j]]

   5. template <typename T>
      class fvector {
      
        public:
      
          void insert(const T & v) {
      
            values.push_back(v);
            indices.push_back(values.size() - 1);
      
            for (int i = values.size() - 1;
      	   (i > 0) && (values[indices[i - 1]] > values[indices[i]]);
      	   i--) {
      	swap(values[indices[i - 1]], values[indices[i]]);
      	swap(indices[i - 1], indices[i]);
      	}
            }
      
      
          int find(const T & v) const {
      
            int l = -1;
            int r = values.size();
            while (l < r - 1) {
      	const int m = (l + r)/2;
      	if (values[indices[m]] <= v)
      	  l = m;
      	else
      	  r = m;
      	}
      
            if ((l > -1) && (values[indices[l]] == v))
      	return indices[l];
            else
      	return -1;
            }
      
        private:
      
          vector<T> values;
          vector<int> indices;
      
        }; // fvector
      

This page last modified on 13 June 2000.