Sorted vs. Unsorted Data Structures, Templates
Participation
Loading...

Export your exercise answers to use with another computer or browser.

Sorted vs. Unsorted Data Structures, Templates

Continuing from last time, we'll consider another potential implementation of a set, this time based on an underlying array that is kept in sorted order. The addition of a sorting invariant means some of our functions are more complicated (i.e. you can't just put elements wherever), but searching for elements in the array can be done much more efficiently.

Finally, it makes sense to introduce templates as a miscellaneous topic here. In particular, templates can be used to implement generic containers with flexible element types (e.g. set<int> and set<string>). Generally speaking, they also complete our exploration (started a few lectures ago) of different kinds of polymorphism.

Updated Fall 2024
1: Time Complexity
1.1 Not Started

As we're asessing the fitness of a data structure for a given task, it's helpful to determine its time complexity, which quantifies how well it performs as the size of the data we're working with scales up. Recall two key types of time complexity:

  • O(1) constant time complexity, where the time taken does not depend on the size of the data, n.
  • O(n) linear time complexity, where the time taken is linearly proportional to the size of the data, n.
1.1 Exercise: Time Complexity

Recall the unsorted IntSet from last time. We used an array for the underlying data representation:

class IntSet {
private:
  int elts[ELTS_CAPACITY];
  int elts_size;
public:
  ...
};

Below are several implementations of functions for the unsorted IntSet from last time. Using a worst-case analysis, determine whether each function has O(1) constant time complexity or O(n) linear time complexity. Explain your reasoning. 

// IntSet constructor
IntSet::IntSet()
  : elts_size(0) { }

IntSet::size() {
  return elts_size;
}

int IntSet::indexOf(int v) const {
  for (int i = 0; i < elts_size; ++i) {
    if (elts[i] == v) {
        return i;
    }
  }
  return -1;
}

bool IntSet::contains(int v) const {
  return indexOf(v) != -1;
}

void IntSet::insert(int v) {
  assert(size() < ELTS_CAPACITY);
  if (contains(v)) {
    return;
  }
  elts[elts_size] = v;
  ++elts_size;
}

void IntSet::remove(int v) {
  if (!contains(v)) {
    return;
  }
  elts[indexOf(v)] = elts[elts_size - 1];
  --elts_size;
}

You're welcome to check your solution with this walkthrough video:

2: A Sorted IntSet
2.1 Not Started

Let's make a key change to the fundamental strategy and data representation for our set - keeping all the elements in sorted order - and see if we can improve the performance of the data structure…


2.1 Exercise: SortedIntSet::insert()

Implement the insert() member function for the SortedIntSet class. If the given value is not already in the set, it should be inserted into the elts array at the appropriate position to maintain the sorting invariant. Elements greater than the inserted value will need to be shifted to the right to create the space to insert the element. elts_size should also increase by 1. However, if the value is already in the array, insert() does nothing.

The main() function provided includes testing code to verify your implementation.

You're welcome to check your solution with this walkthrough video:

Note: This walkthrough uses several different files for the code, which is different than the above, where we had everthing embedded into one file. (The solution for insert() is the same, though!)

3: Templates
3.1 Not Started

Finally, let's use templates to implement a generic set container with a flexible element type.


3.1 Exercise: fillFromArray() Function Template

Fill in the blanks to make the function work as intended (the main function shows examples).

template <>
void fillFromArray( set,  arr, int n) {
  for (int i = 0; i < n; ++i) {
    
  }
}
int main() {
  UnsortedSet<int> set1;
  int arr1[4] = { 1, 2, 3, 2 };
  fillFromArray(set1, arr1, 4); // set1 now contains 1, 2, 3
  UnsortedSet<char> set2;
  char arr2[3] = { 'a', 'b', 'a' };
  fillFromArray(set2, arr2, 3); // set2 now contains 'a', 'b'
}

You're welcome to check your solution with this walkthrough video:
You've reached the end of this lecture! Your work on any exercises will be saved if you re-open this page in the same web browser.

Participation Credit
Make sure to sign in to the page, complete each of the exercises, and double check the participation indicator at the top left of this page to ensure you've earned credit.