Consider the following consecutive configurations of a list while it it being
- (4, 5, 3, 1)
- (4, 5, 3, 1)
- (4, 3, 5, 1)
- (4, 3, 1, 5)
What sorting algorithm is being used?
What is the best case running time of Bubble Sort?
often a term in the efficiency expressions for divide and
What sort might you use if you know that your data will be pretty much in order
to begin with and why would you use that sort?
Imagine that we run quick sort on an already ordered list, picking the pivot by
the first element. What problem do we run into?
Why are merge sort and quick sort known as "divide and conquer" algorithms?
Why might it seem counterintuitive that heap sort can run so efficiently?
Merge sort is
. Where does the n term come from?
Which of the following is a proper heap?
For merge sort to merge the following two arrays: (1, 4, 5, 8) and (3, 7, 9,
13), what comparisons have to take place?
Consider a sorting algorithm that checks all possible configurations of a list
until it finds one that is in order. This algorithm will sort a list correctly,
but is very inefficient. What is its big-O notation?
In what case is the algorithm described above as efficient as bubble sort?
In what case is the algorithm described above more efficient than
Consider the intermediate configurations of an array being sorted below. What
sort is being used?
- (4, 5, 2, 1, 7)
- (1, 5, 2, 4, 7)
- (1, 2, 5, 4, 7)
What sorting algorithm might you choose for the following list? Why?
(1, 2, 3, 6, 5, 9)
True of false: merge sort and quick sort can only be used on lists whose length
is a power of 2.
How many comparisons would it take merge sort to merge the following lists: (1,
2, 3, 4, 5) and (6, 7, 8, 9, 10)?
True or false: selection sort can sometimes run as fast as
The intermediate configurations below are characteristic of which sorting
- (5, 1, 4, 8, 2)
- (1, 5, 4, 8, 2)
- (1, 4, 5, 8, 2)
- (1, 4, 5, 2, 8)
Why would it be a bad idea to implement heap sort using a heap data structure
that didn't support random access?
Imagine the following strategy for picking a pivot in quick sort: scan through
half the data set, and use the median value as the pivot. Why is this a bad
Imagine the following specification of a comparison function. If the two
numbers passed in have an equal number of digits, they are equal. Otherwise,
the one with the larger number of digits is greater. Which of the following
lists are sorted with respect to this comparison function?
Why are we so concerned with the efficiencies of sorting algorithms?
Imagine a comparison function for complicated objects. Why might efficiency
calculations for a sort using this comparison function be misleading?
Consider the following intermediate configurations of a list being sorted. What
sorting algorithm is being used?
- (5, 2, 8, 1, 9)
- (1, 5, 2, 8, 9)
- (1, 2, 5, 8, 9)
What is the first swap insertion sort would make on the following list?
(5, 3, 4, 9, 1)
What is the first swap selection sort would make on the following list?
(5, 3, 4, 9, 1)
What kind of data structure would make insertion sort particularly
Imagine a situation where most of the data to be sorted starts in roughly
reverse order. Why would this not be a good situation to use bubble sort?
What simple modification could be made to bubble sort to make it efficient in
the situation described above?
Why would bubble sort be more efficient on the list (1, 2, 3, 4, 5, 6, 7) than
When using quick sort, why is it common to switch to another sort when the lists
being sorted are small?
In what situation might heap sort be useful?
What makes heap sort attractive as opposed to quick sort?
Why is quick sort's name misleading?
True or false: bubble sort gains efficiency by splitting the data in half.
Why is sorting important to the process of searching?
True or false: for some data sets, quick sort will be slower than bubble sort.
How long does re-heaping take?
True or false: selection sort's efficiency is independent of the data being