The purpose of this quiz is to give you a chance to review your knowledge of topics involving searching for and sorting data in C-style arrays.
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(char array[], size_t start, size_t end)
{
size_t loop{start}, cur;
bool done{false};
while ( loop <= end && ! done )
{
done = true;
for ( cur = start; cur <= end-1; ++cur )
{
if ( array[cur] < array[cur+1] )
{
swap(array[cur], array[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 function:
size_t locate(long a[], size_t M, long f)
{
size_t i = M-1;
while ( i >= 0 && a[i] != f )
{
i--;
}
return (i < 0) ? -1 : 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 array.
f is being compared to each array 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 array argument being changed? What should you do to show this more clearly?
No, the array 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_ts
for the indices as is appropriate for an array 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 an array of double values instead of an array 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 for this.
size_t locate(double a[], size_t M, double f)
size_t i = M-1;
while ( i >= 0 && abs(a[i] - f) > 1e-6 )
Write a function to perform a binary search of a character array.
inline size_t binary_search(const char a[], size_t size, char target)
{
auto mid{size}, // set up for empty issue
bot{mid}, top{mid}; // init required for auto
if ( size > 0 )
{
bot = 0;
top = size - 1;
mid = (bot + top) / 2; // average for middle
while ( bot < top && // more elements to search thru
a[mid] != target ) // not what we want
{
if ( a[mid] < target ) // target falls above middle
{
bot = mid + 1; // move bottom up just past middle
}
else // a[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 a 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 array in a similar way. This continues until the entire array
has been brought into the sorted portion.