CS 14 - Fluency Exercises

Programming Exercise: Set Comparisons - Sorting

In this exercise, we will develop a technique for comparing the contents of two multi-sets (the mathematical term "set" means roughly "group of items whose order doesn't matter, which cannot have duplicated values." "Multi-set" means "set of items where each value may be duplicated an arbitrary number of times.")

Remeber that to use vectors you need to have #include <vector> in your file.

STL Lists

Here is a very quick primer on the basic functionality for STL lists. (Note that the STL list type is a doubly-linked list, so insert and remove operations on both ends are efficient. A more space-efficient type, slist is also available, which has essentially the same interface.)

Gaining access to the STL vector type
```
#include <vector>
```
Declaring a vector of ints:
```
vector<int> myVec;
```
Adding to the back of the vector:
```
myVec.push_back(10);
```
Getting or setting a value in a vector (just like an array)
```
int val = myVec[5];
myVec[2] = 42;
```

Iterating through the vector:

unsigned int size = myVec.size();
for (unsigned int i = 0; i < size; i++)
{
  cout << myVec[i] << endl;
}

For example, a recursive function to sum the elements of a list would be:

int listSum(list<int> l)
{
  int front = l.front();
  l.pop_front();
  
  if (l.size != 0) return front + listSum(l);

  return front;
}

3 points

Write a function bool isSameList(const vector<int>& l1, const vector<int>& l2); that takes two sorted lists and decides if they are the same.
Write a function int minIndex(const vector<int>& l, int n); that finds the index of the minimum element in l at or after the nth position. For example, if l is the list [1, 3, 4, 2, 5, 9] and n is 2, then we want to return the index of 2, since it is the smallest element after position 2.
Write a function void selectSwap(vector<int>& l, int n); that uses minIndex above and swaps the nth element with the smallest element after n.
Write a function void selectionSort(vector<int>& l); that uses selectSwap to sort the list l.
Write a function bool isSameSet(vector<int> l1, vector<int> l2); that uses selectionSort and isSameList to decide if two unsorted lists are made up of the same values repeated the same number of times (that is, one is just a permutation of the other).

Extra Credit Options

2 points: Rewrite all of these functions only using while loops (no for loops).
4 points: Rewrite all of these functions without any loops at all, only recursion.