EEN218 Very Easy Test 18^th April 2002, Sample Solutions

5. “Tell me all about Quicksort”:

Explain how quicksort works.

Quicksort is naturally implemented as a recursive function, which is passed as parameters the array to be sorted and the bounds of the sort (i.e. sort this array between positions a and b). If the distance between a and b is only one, there is no work to do; otherwise quicksort does its job.

The first step is to partition the array. A 'pivot' is selected (an element of the array that we hope will turn out to be near the middle when the array is sorted, but there are no guarantees), and the elements of the array are rearranged one-by-one so that all elements less than the pivot are to the left of it, and all elements greater than the pivot are to the right of it.

This results in a slightly sorted array. Most of the elements are out of order, and clearly more sorting is required, but the important thing is that the pivot is guaranteed now to be in the right place. Even though most of the other elements are probably going to have to move, we know they won't have to move very far. Everything that is left of the pivot really belongs left of the pivot, and everything that is right of the pivot really belongs right of the pivot.

The sorting operation is completed by simply applying quicksort recursively to the two partitions of the array: everything to the left of the pivot is sorted, then everything to the right of the pivot is sorted, both operations performed as complete self-contained (but smaller) sorts.

What are the advantages and disadvantages of quicksort, compared to other sorting algorithms?

Quicksort is normally expected to be very fast, t=O(n×log₂n), so that is a major advantage over all of the simpler algorithms (e.g. selection, insertion, and bubble sorts). Also, it requires no extra memory, which is an advantage over merge-sort. However, quicksort can, in unfortunate circumstances (when the original array is already sorted or nearly sorted) slow down to O(n²), which is a significant disadvantage when compared to mergesort.

How fast is quicksort?

t=O(n×log₂n)

Why is quicksort that fast?

When sorting an array of n elements, the partitioning phase simply inspects each element once, and in a very simple operation moves it to the right place, so partitioning is O(n).

If the pivot did turn out to be near the middle of the partitioned array (and on average, it does) then the next step will to be to recursively sort two arrays each of about ½n elements, so there will then be two further partitioning operations each dealing with ½n items, for t=2×O(½n)=O(n).

After each of those ½n partitioning operations, there will be 4 sub-arrays, each of size approximately ¼n, requiring time time 4×¼n=n, and resulting in 8 sub-arrays each of size ⅛n, requiring time 8×⅛n=n. This process continues in a similar fashion until the sizes of the sub-arrays are so small that there is no work to do.

How long does this take? At each stage, the expected size of the sub-arrays is halved, so how many times can you halve n before it is reduced to 1? (½)^xn=1 has x=log₂n as its solution. So the number of stages is log₂n, and each stage is t=O(n), so the total time is O(n×log₂n), if the pivots do indeed turn out to be as expected.

If it takes a particular implementation of quicksort 1mS (0.001 sec.) to sort an array of 1000 data items, how long would you expect it to take to sort an array of 1000000 data items? (show your calculations)

t=O(n×log₂n) means that time taken is k×n×log₂n for some unknown k. With knowledge of just one set of corresponding values for t and n, we can work out what k is: k=t¸(n×log₂n).

So, given n=1000 (10³) produces t=1mS (10^-3), k = 10^-3¸(10³×10) = 10^-7.

Now, when n=1000000 (10⁶), t=k×n×log₂n is a simple calculation: 10^-7×10⁶×20 = 2. We should expect it to take about 2 seconds to sort a million items.

6. All about pointers:

There are two really important things to remember for this sort of question: Priorities of operators – [ ] denoting an array, and ( ) denoting a function, are high priority; * denoting a pointer is low priority. Use parentheses to help clarify. Secondly, you must remember that C and C++ can not tell the difference between a pointer to a single thing and a pointer to a whole array of things. * denotes both "pointer-to" and "pointer-to-array-of" equally.

Write complete and correct C++ declarations for the following things:

a) an integer variable

int a;

b) an array of 300 strings

string b[300];

c) a pointer to a string

string *c;

d) a pointer to an array of 400 integers

int *d;

Remember C/C++'s illogical system: "pointer-to" and "pointer-to-array-of" are the same thing, as far as it can tell. But you would have got partial credit for this wrong-but-logical answer:

int (*d)[400];

e) an array of 500 pointers to strings

string *e[500];

or equally correct:

string *(e[500]);

f) a pointer to an array of 600 pointers to integers

int **f;

or equally correct:

int *(*f);

for the same reason as with d, but for partial credit:

int *(*f)[600];

or

int *((*f)[600]);

Say in plain but precise English what the following declarations declare:

(assuming that a struct or class called “person” has already been declared)

g) person *one[100];

Remembering that [ ] has higher priority than *, the name "one" is most closely associated with the [100] than with the *, so one is an array of 100 pointers to integers.

h) person **two;

Remembering the dual meaning of *, there are four things this declaration could mean:

two is a pointer to a pointer to a person object, or

two is a pointer to an array of pointers to person objects, or

two is a pointer to a pointer to an array of person objects, or

two is a pointer to an array of pointers to arrays of person objects.

i) person *three(int x);

Remembering the priorities again, the ( ) is more binding than the *, so three is a function, not a pointer. Three is a function that takes an integer parameter and returns as its result a pointer to a person object.

If a function is needed to create a person object using input from the user, and return a pointer to that object ready to be stored in an array for later use, one might write something like this:

person *make_a_person(void)

{ person p;

string s;

cout << “What is the person’s first name? “;

cin >> s;

p.fname = s;

cout << “and what is their last name? “;

cin >> s;

p.lname = s;

return &p; }

but something is seriously wrong with that design. What?

This function creates a temporary person object in the variable p. Like all temporary objects, it will cease to exist as soon as the function finishes. At the end of the function, a pointer to this temporary object is returned. So the function returns as its result a pointer to an object that no longer exists.

I need something that behaves like an array of persons, but its size can be changed while the program is running. I don’t know how many persons I am likely to need to store: it could be an enormous number, and it could be very few, but I don’t want to waste too much memory.

Show me how to declare such a thing in C++, and how to use it properly (how to store data in it, how to access that data, and how to change its size).

Note that I am only concerned with having a flexible size and being fairly efficient with memory use. I am not concerned with error detection.

For efficiency (as requested by the question), we should be dealing with pointers to person objects. As arrays can't really be resized, we need to be able to discard an old array that turns out to be the wrong size and replace it with a new one. So what we need is a pointer to an array of pointers to person objects. From the first part of this question, we know that the declaration should be:

person **data;

together with

int size;

so that we can remember how big the array is at the moment.

We would need to pico an initial size, let's say 10, but it could be anything and add assignments:

int size=10;

person **data = new (person *)[size];

How to store something in the array: first make sure its big enough, resize if not; then simply assign:

// storing value v at position p: (v is a pointer-to-person, p is an int)

if (p>size)

resize(p+1);

data[p]=v;

Retrieving a value from the array can still check that the index is valid, but probably should not resize if it isn't:

// extracting value from position p and stroing it in variable x:

if (p<size)

x=data[p];

else

error...

And finally the resize function. This should first create a new array of the right size, then copy as much from the old array as will fit, then recycle the old array and start using the new one instead:

void resize(int newsize)

{ person **n = new (person *)[newsize];

for (int i=0; i<size && i<newsize; i+=1)

n[i] = data[i];

delete[ ] data;

data = n;

size = newsize; }

7. What on earth is this supposed to be?

It is an ant wearing a hat, being disappointed by a ham sandwich.

What appears to be an extra leg at the back, and caused some people to think he must be a spider, is in fact a vestigial tail. It is quite rude to point out deformities in others, especially under examination conditions, so I am glad that so few of you mentioned it.

The ant is not being swept up by the wind; he is in that position because he is preparing to pounce on his prey. All the great hunting species pounce, even on prey that has disappointed them.

He is disappointed because the sandwich was made with mayonnaise instead of butter.

The hat is intended to protect him when stamped on by irate formicophobic humans. You may think that is a foolish form of protection, but he is only an ant; there is barely room for a single neuron inside that tiny little head, so I think he is doing quite well really.