The purpose of this quiz is to give you a chance to review your knowledge of topics involving searching for and sorting data in a vector.
Explain how selection sort attempts to improve on the design of bubble sort.
Selection sort attempts to reduce the number of memory movements that
bubble sort takes.
Is it successful? Why/Why not?
Yes! It reduces from a quadratic number of memory movements to a linear
count.
Of course, it doesn't reduce the number of comparisons, so its time
complexity remains quadratic, but it is something impactful when data
items take up a lot of memory.
When sorting n elements with an insertion sort, we need _____ comparisons (on average).
When using a linear search to find data we will take linear comparisons (on average). If we sort the data first, though, we can use a binary search to find data. This search takes only log(n) comparisons to find the information. (If we graph these two functions we can easily see that linear search is the looser.)
Given the following sort function:
void decent_sort(vector<char> & vec,
vector<char>::size_type start,
vector<char>::size_type end)
{
vector<char>::size_type loop = 0;
vector<char>::size_type cur;
bool done = false;
while ((loop < end-start) && !done)
{
done = true;
for (cur = start; cur != end-2; cur++)
{
if (vec[cur] > vec[cur+1])
{
swap(vec[cur], vec[cur+1]);
done = false;
}
}
loop++;
}
return;
}
Explain how this sort works.
It compares next-door neighbors to see if they are out of order and, if so,
swaps them to put them in order. If this happens, we moved data and so we
are not done with the sort. But, before walking to all the neighbors, we
assume we are all the way done -- hopeful, aren't we?
This inner loop puts a single piece of data in place each time it is run.
The outer loop keeps us going until all but one item has been put in place
or until we succeed in being done with the sort for the neighbor pass.
What order are the sorted elements in (ascending, descending, etc.)?
Since the lower item being greater than the higher item is out of order,
the overall sorted order will be non-decreasing. If all items are unique
we could call this ascending.
How would you change the code to reverse that order?
To change the order just change the > to a < in the if condition
of the inner loop.
Given the following typedefs and function:
typedef vector<long> LVlist;
typedef LVlist::size_type LVsize;
typedef LVsize LVposit;
LVposit locate(LVlist & a, LVsize M, long f)
{
LVposit i = M-1;
while ((i >= 0) && (a[i] != f))
{
i--;
}
return (i < 0) ? M : i;
}
What are the parameters M and f? (Their meaning...)
M is used as both a starting position -- well, one more than, anyway
-- and an error flag return at the end. It must be the Maximum number
of items in the vector.
f is being compared to each vector element in turn. It must be
the value to find during the search.
Is this a binary or linear search?
It is a linear search.
Why is i being decremented? (As opposed to being incremented...)
i starts at the end of the list -- its last item -- and moves toward
the beginning of the list. Thus it must be decremented rather than
incremented.
Is the vector argument being changed? What should you do to show this more clearly?
No, the vector argument is not changed. We should mark it const to
make this more clear to any callers and to the compiler.
Will this function work? (Will it even compile quietly?)
It will not compile quietly. The >= 0 condition will cause a warning
that it is always true. This is because we are using size_types
for the indices as is appropriate for a vector search. But such types
are always unsigned and therefore always >= 0. Thus the decrement
inside the loop will not give a -1 at the end but wrap to the maximum value
for its bit-size.
To fix this warning that leads to an infinite loop error we need to check
for the wrap-around condition instead of >= 0. This is done by checking
that the index +1 is strictly greater than 0 -- no equal to. When this
fails, we will have wrapped around.
Rewrite the locate function above to search a vector of double values instead of a vector of long values. (Reminder: you cannot use == or != with double without the compiler complaining. How can you remove its concerns relatively easily?)
You need show only the code that must change.
typedef vector<double> DVlist;
typedef DVlist::size_type DVsize;
typedef DVsize DVposit;
DVposit locate(DVlist & a, DVsize M, double f)
DVposit i = M-1;
while ((i >= 0) && (abs(a[i] - f) > 1e-6))
Write a function to perform a binary search of a character vector.
inline vector<char>::size_type binary_search(const std::vector<char> & v,
char target)
{
auto mid{v.size()}, // set up for empty issue
bot{mid}, top{mid}; // init required for auto
if ( ! v.empty() )
{
bot = 0;
top = v.size() - 1;
mid = (bot + top) / 2; // average for middle
while ( bot < top && // more elements to search thru
v[mid] != target ) // not what we want
{
if ( v[mid] < target ) // target falls above middle
{
bot = mid + 1; // move bottom up just past middle
}
else // v[mid] > target -- target falls below middle
{
top = mid; // move top down to middle
}
mid = (bot + top) / 2;
}
}
return mid; // item is either at mid or not or size if v was empty
}
The sorts we've explored are not the fastest available. They are the easiest to understand. How many comparisons (on average) do each of the following sorts take?
n*log(n)
n*log(n)
n*log(n)
What other properties are used to distinguish between the above three sorts?
Stability, worst number of comparisons, and extra memory usage.
Briefly explain how insertion sort works.
Insertion sort first says that the first item in the list is -- by itself
-- sorted! Then it looks to bring the second item into this already
sorted list in the proper position: in front of the first item or where
it already is. After moving it to the proper position if necessary, it
will have a sorted list of two items.
Then it brings the third and fourth and so on items into the already sorted
part of the vector in a similar way. This continues until the
entire vector has been brought into the sorted portion.