DSABook – Review questions

3.9 Review questions

This final section contains some review questions about the contents of this chapter.

3.9.1 Review questions: Terminology

Which of these is the best definition for a stable sorting algorithm?

An algorithm that does not change the relative ordering of equal elements
An algorithm that is as fast as the best one known
An algorithm that always gives the right answer
An algorithm that always gives the same order for duplicate keys from run to run

“Stable” has nothing to do with how fast an algorithm is.
It refers to maintaining the relative order of elements that compare equal.

Which of these will NOT affect the RELATIVE running times for two sorting algorithms?

The CPU speed
The number of elements
The allowable range for the values
The amount by which the values are out of order

If we speed up the CPU by a factor of two, both sorts will go twice as fast.

Which of these is a traditional measure for the cost of a sorting algorithm?

Note: Multiple answers are possible!

This question does not ask what affects the cost. It asks what is a measure of the cost.
The number of elements affects the cost, but it does not measure the cost.
The memory size affects the cost, but it does not measure the cost.
Elements being out of order can increase the cost, but not measure it.

In which case might the number of comparisons not be a good representation of the cost for a sorting algorithm?

When we are comparing strings of widely varying length
When there are lots of elements
When the CPU is really fast
When the amount of available space is small

CPU speed would affect all comparisons in the same way.
Number of elements or amount of space won’t affect the value of counting comparisons.
The longer the string, the longer it takes to compare.

Sometimes, the constant factors in an algorithm’s runtime equation are more important thant its growth rate. When the problem is sorting, this can happen in which situation?

When we are sorting lots of small groups of elements.
When there are lots of elements.
When the CPU is really fast.
When the amount of available space is small.
When the elements are nearly sorted.
When the elements are nearly reverse sorted.

CPU speed would affect all comparisons in the same way.
Elements being sorted or reverse sorted affects the growth rate of different algorithms differently. But not relevant to this question.
When we sort only a few elements, constants matter a lot.

3.9.2 Review questions: Bubble sort

Here are some review questions to check your understanding of Bubble sort.

Answer TRUE or FALSE.

Bubble sort (as the code is written in this chapter) is a stable sorting algorithm.

(Recall that a stable sorting algorithm maintains the relative order of equal elements.)

True
False

Remember that: Bubble sort consists of a simple double for loop.
The first iteration of the inner for loop moves through the array from bottom to top, comparing adjacent elements.
If the lower-indexed element is greater than its higher-indexed neighbour, then the two are swapped.

In which cases are the time complexities the same for Bubble sort (as the algorithm is presented in this chapter)?

Worst, Average and Best
Worst and Best
Best and Average
Worst and Average

Does Bubble sort’s cost vary according to the order of the array input values?
No, it does not matter what order the input values have.

The order of the input records has what impact on the number of comparisons required by Bubble sort (as presented in this chapter)?

None.
There is a constant factor difference.
There is a big difference, the asymptotic running time can change.

Does Bubble sort change when it make a comparison according to the order of the array input values?
No, it does not matter what order the input values have.

What is the worst-case time for Bubble sort (as the algorithm is presented in this chapter) to sort an array of $n$ records?

Does Bubble sort’s number of comparisons depend on the particular order of the input array?
No, it does not.

What is the running time of Bubble sort when the input is an array where all elements are equal?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

Each comparison test in the inner for loop will fail because the value at position $i$ is never less than the value at position $i-1$ .
However, this observation does not affect the number of comparisons to be made, it only affects the number of swaps.

What is the running time for Bubble sort when the input array has values that are in reverse sort order?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

On each iteration, the $i$ th record will have to move to the start of the array.
This is the worst case.

What is the running time of Bubble sort (as the algorithm is presented in this chapter) when the input is an array that has already been sorted?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

Each test in the inner for loop will fail because the value at position $i$ is never less than the value at position $i-1$ .

When is Bubble sort a good choice for sorting an array?

There is no situation where Bubble sort is the best choice over all of the others in this chapter.
Each component of the array requires a large amount of memory.
Each component of the array requires a small amount of memory.
The array has only a few items out of place.

Does Bubble sort’s cost vary with how much the input is out of order?
Bubble sort always does a lot of work, as compared to other sorting algorithms.

In the worst case, the total number of comparisons for Bubble sort is closest to:

Bubble sort’s implementation is made up of two nested for loops.
The outer for loop is executed $n-1$ times.
The inner for loop is executed $i$ times.
The total cost is the sum of $i$ ’s for $i$ goes from 1 to $n$ .

3.9.3 Review questions: Selection sort

Here are some review questions to check how well you understand Selection sort.

Answer TRUE or FALSE.

Selection sort is simple, but less efficient than the best sorting algorithms.

True
False

What is Selection sort’s worst case complexity?
It is $O(n^2)$ .
Are there any better sorting algorithms?

Answer TRUE or FALSE.

Selection sort (as the code is written in this chapter) is a stable sorting algorithm.

(Recall that a stable sorting algorithm maintains the relative order of equal elements.)

True
False

Can you find a counter-example to the proposition?
What about the array [2,2,1]?
Will the relative order between the two 2’s change while sorting?

Suppose that Selection sort is given an input of 100 elements, and it has completed 37 iterations of the main loop.

How many elements are now guaranteed to be in their final position (never to be moved again by the sort)?

On each pass, Selection sort puts a element into its final position.
So, if Selection sort has done $k$ passes, then at least $k$ elements are in their final positions.

How many times does Selection sort call the swap function on an array of $n$ records?

Selection sort first finds the smallest element in an unsorted list, then the second smallest, and so on.
To find the next smallest element requires searching through the entire unsorted portion of the array, but the search itself needs no swaps.
Once the next smallest element is found, one swap is required to put the element in place.
We don’t need to check anything on the very last pass, since at that point the last element must already be in place.

In which cases are the time complexities the same for Selection sort?

Worst, Average and Best
Worst and Best
Best and Average
Worst and Average

Does Selection sort’s cost vary according to the order of the array input values?
No, it does not matter what order the input values have.

The order of the input records has what impact on the number of comparisons required by Selection sort (as presented in this chapter)?

None
There is a constant factor difference
There is a big difference, the asymptotic running time can change

Does Selection sort change when it make a comparison according to the order of the array input values?
No, it does not matter what order the input values have.

What is the worst-case time for Selection sort to sort an array of n records?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

Does Selection sort’s order and number of comparisons depend on the particular order of the input array?
No, it does not.
Recall that our implementation for Selection sort will try to swap even if the current record is in its correct location.

What is the running time of Selection sort when the input is an array that has already been sorted?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

Each test in the inner for loop will be the same no matter what the order of the input array.

What is the running time of Selection sort when the input is an array that has all equal values?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

Each test in the inner for loop will be the same no matter what the order of the input array.

Which statement best characterises Selection sort (as the code is written in this chapter)?

(Recall that a stable sorting algorithm maintains the relative order of equal elements.)

Selection sort is not stable, but with minor modifications it could be made so
Selection sort is stable
Selection sort is not stable

Think of the behaviour of every pass through the inner for loop of Selection sort if two elements are equal, with the smallest value in the array.
Which element will be selected?
The last such element.
It will be moved to the first position in the array, putting it out of order with other equal elements.
But we could easily change the minimum-finding part of the loop to take the last of these equal elements.

In the worst case, the total number of swaps done by Selection sort is closest to:

$n$
$n^2/2$
$n^2$
$n \log n$

Does Selection sort’s number of swaps depend on the particular order of the input array?
No, it does not.
Recall that our implementation for Selection sort will try to swap even if the current record is in its correct location.

When is Selection sort a good choice to use for sorting an array?

When the cost of a swap is large
When each component of the array requires a small amount of memory
When the array has only a few elements out of place
None of these answers

The big advantage of Selection sort is that it keeps the number of swaps small.
So it will make best use of this advantage when the cost to swap is large.

In the worst case, the total number of comparisons for Selection sort is closest to:

Selection sort’s implementation is made up of two nested for loops.
The outer for loop is executed $n-1$ times.
The inner for loop is executed $n-i$ times.
The total cost is the sum of $i$ ’s for $i$ goes from 1 to $n$ .

3.9.4 Review questions: Insertion sort

Answer TRUE or FALSE.

Insertion sort (as the code is written in this chapter) is a stable sorting algorithm.

(Recall that a stable sorting algorithm maintains the relative order of equal elements.)

True
False

Think of the behaviour of every pass through the inner for loop of the Insertion sort if the elements are equal.

When implementing Insertion sort, a binary search could be used to locate the position within the first $i-1$ elements of the array into which element $i$ should be inserted. Using binary search will:

Not speed up the asymptotic running time because shifting the elements to make room for the insert will require $O(i)$ time.
Speed up the asymptotic running time because the position to insert will be found in $O(\log i)$ time.
Speed up the asymptotic running time because shifting the elements to make room for the insert will require $O(i)$ time.
None of these answers is correct.

The position at which to insert could be found in $O(\log(i))$ steps, but shifting the elements to make room for the this element will require $O(i)$ time.

When implementing Insertion sort, a binary search could be used to locate the position within the first $i-1$ elements of the array into which element $i$ should be inserted. In this implementation, the worst case time will be:

$O(n^2)$
$O(n \log n)$
$O(n)$
$O(\log n)$

The position to insert could be found in $O (\log i)$ , but shifting the elements to makeroom for the insert will still require $O(i)$ time

We know that the worst case for Insertion sort is about $n^2/2$ , while the average case is about $n^2/4$ . This means that:

The growth rates are the same
The runtime in the average case is about half that of the worst case – [x] Both of the above
None of the above

Growth rates ignore constants.

In which cases are the growth rates the same for Insertion sort?

Worst and Average only
Worst and Best only
Best and Average only
Worst, Average, and Best

Insertion sort is really cheap in the best case.
Its average and worst case times differ by a constant factor.

The order of the input elements has what impact on the number of comparisons required by Insertion sort (as presented in this chapter)?

There is a big difference, the asymptotic running time can change
None
There is a constant factor difference

Does Insertion sort change when it make a comparison according to the order of the array input values?
Yes, Insertion sort might stop early or might look at many elements.

What is the worst-case time for Insertion sort to sort an array of n elements?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

In the worst case, each element must make its way to the start of the array. This would occur if the elements are initially arranged from highest to lowest, in the reverse of sorted order.
In this case, the number of comparisons will be one the first time through the for loop, two the second time, and so on.

What is the best-case time for Insertion sort to sort an array of n elements?

$O(n)$
$O(n^2)$
$O(\log n)$
$O(n \log n)$

The best-case cost occurs when the elements are already in sorted order from lowest to highest.
In this case, every test on the inner for loop will fail immediately, and no elements will be moved.

What is the running time of Insertion sort when the input is an array where all elements are equal?

Each test in the inner for loop will fail because the value at position $i$ is never less than the value at position $i-1$ .

If $i$ is the number of inversions in an input array of $n$ elements, then Insertion sort will run in what time?

Insertion sort has to do $n$ passes where it compares at least once.
If the element for this pass has no remaining inversions, then it requires no work.
But if it does have inversions, it will need a swap for each such inversion.

What is the running time for Insertion sort when the input array has values that are in reverse sort order?

$O(n^2)$
$O(n)$
$O(\log n)$
$O(n \log n)$

On each iteration, the $i$ th element will have to move to the start of the array.
This is the worst case.

What is the running time of Insertion sort when the input is an array that has already been sorted?

$O(n)$
$O(n^2)$
$O(\log n)$
$O(n \log n)$

Each test in the inner for loop will fail because the value at position $i$ is never less than the value at position $i-1$ .

When is Insertion sort a good choice for sorting an array?

Note: Multiple answers are possible!

The array has only a few elements out of sorted order
The array contains only a few elements
Each element requires a large amount of memory
Each element requires a small amount of memory
The processor speed is fast
The array contains many elements
None of these situations
We need a reasonably fast algorithm with a good worst case

Insertion sort if fairly simple.
Because Insertion sort is simple, it tends to cost only a little bit per comparison when compared to more complicated sorting algorithms.
Remember that Insertion sort implementation is made up of two nested for loops.
The outer for loop is executed $n-1$ times. While the number of times the inner for loop executes depends on how many keys in positions 0 to $i-1$ have a value less than that of the key in position i.

In the worst case, the total number of comparisons for Insertion sort is closest to:

$n^2/2$
$n$
$n^2$
$n \log n$

Insertion sort’s implementation is made up of two nested for loops.
The outer for loop is executed $n-1$ times.
The inner for loop is executed $i$ times.
The total cost is the sum of $i$ ’s for $i$ goes from 1 to $n$ .

3.9.5 Review questions: Exchange sort

Answer TRUE or FALSE.

Consider an array $A$ of $n$ records each with a unique key value, and $A_R$ the same array in reverse order. Any given pair of records must be an inversion in exactly one of $A$ or $A_R$ .

True
False

Any given pair of records with different values is either in order, or not in order.
Being out of order is called an inversion.
If your pair is in order in some array, then it must be out of order in the reverse.

Answer TRUE or FALSE.

Consider an array $A$ of $n$ records each with a unique key value, and $A_R$ the same array in reverse order. There are a certain number of pairs, where an arbitrary position $i$ and position $j$ is a pair. Between these two arrays, exactly half of these pairs must be inverted.

True
False

Any given pair of records with different key values is either in order, or not in order.
Being out of order is called an inversion.
Any given pair must be inverted in exactly one of these arrays.
So every pair must be inverted in either $A$ or $A_R$ .

The average number of inversions in an array of $n$ records is $n(n-1)/4$ . This is:

$O(n^2)$
Better than $O(n^2)$
Worse than $O(n^2)$

$n(n-1)/4 = n^2/4 - n/4$ .
From the rules on asymptotic analysis, $O(n^2/4 - n/4)$ is $O(n^2)$

An exchange sort is:

Any sort where only adjacent records are swapped
Any sort where records are swapped rather than using another mechanism for rearranging the array
Another name for Insertion sort
Any $O(n^2)$ sort
Any $O(n)$ sort

Most of the sorts that we study swap records.
Insertion sort is not the only exchange sort.
An “exchange” means a swap of adjacent records.

An inversion is:

When a record with key value greater than the current record’s key appears before it in the array
A swap
A type of sort

We have not used “inversion” to refer to a type of sort.
While “inversions” are related to swaps (since ultimately a swap is needed to undo an inversion), it is not a swap.
Inversion refers to an instance of a record being out of order.

How many ways can $n$ distinct values be arranged?

There are $n$ ways to pick the first record.
That leaves $n-1$ ways to pick the second record.
This means that there are $n * (n-1)$ ways to pick the first two records.
And so on.

If $i$ is the number of inversions in an input array of n records, then Insertion sort will require how many swaps?

An inversion requires a swap to undo it.
The number of comparisons done by an algorithm is generally different from the number of swaps.

The total number of pairs of records among $n$ records is:

There are $n$ ways to pick the first record in the pair.
This leaves $n-1$ ways to pick the second record.
We consider pair (A, B) to be the same as pair (B, A).