| Algorithms for Sorting |
About This Exercise
This exercise is based on material presented during the lectures on October 31 and November 3.
The objectives of this exercise are
- to ensure that you understand the definition of the sorting problem that was discussed;
- to ensure that you understand the algorithms for sorting
(including Selection Sort, Insertion Sort, Bubble Sort
and Merge Sort) that were presented in these lectures.
You should be able to
- trace the execution of these algorithms by hand on small examples,
- explain what these algorithms do, both by giving simple English descriptions and providing pseudocode for them,
- understand the proofs of correctness and efficiency of these algorithms, and
- understand and be able to apply the results that were presented about the worst-case running times of these algorithms;
- to ensure that you could implement these algorithms by writing Java programs for them (and, ideally, writing programs using other programming languages as well).
Please read through and try to solve the problems on this exercise before attending the tutorials on November 10-12. Problems on this exercise will be discussed in this and the following tutorial.
Problems
-
Consider the following array A.
Trace the execution of each of the following sorting algorithms on this input array:
- Selection Sort
- Insertion Sort
- Bubble Sort
- Merge Sort
-
Repeat the above question using the following array A instead. Which (if any) of the algorithms are significantly faster when run on this array than they were when run on the previous one?
-
Give a description in English (using pictures, where appropriate) for the conditions that are included in the “loop invariant” for the inner loop of Bubble Sort.
Descriptions in English (using pictures) for the conditions included in the loop invariant for the inner loop of Selection Sort and Insertion Sort were provided during the lecture on this topic. If it is helpful, these can be used as examples of what should be provided here.
-
Give a loop invariant and loop variant for the inner loop of the version of the “Bubble Sort” algorithm that is found in the lecture notes and that was presented during the lecture on classical sorting algorithms.
-
Several students have seen a different version of Bubble Sort already — namely, one in which passes are made from the left to the right instead of from the right to the left.
The Wikipedia article on Bubble Sort includes pseudocode for one such algorithm.
Informally describe the conditions that are achieved (bringing the array closer to being sorted) after the outer loop of this algorithm has been executed k times for an integer k≥0.
Then, provide a more formal “loop invariant” for the outer loop of this algorithm.
Note: Students who are not particularly interested in this question might find the Wikipedia article to be interesting, or entertaining, for other reasons. (The course instructor certainly did.)
-
Recall that a recursion stack (possibly, also called an “activation stack”) is maintained when a recursive program like “Merge Sort” is executed.
Consider the contents of this stack at some point during the execution of Merge Sort, given an input array whose size is a power of two, n=2k.
- What is the maximum size of this stack? That is, how many “activation records” might be on the stack at any particular time?
- Notice that every such activation record corresponds to a call to Merge Sort with an array of some size between one and n as input. What are the sizes of arrays corresponding to activation records, at any time?
- Try to show that the sum of the sizes of these arrays is always at most linear in n.
The last result is important because that it can be used to argue that Merge Sort is reasonably “space efficient:” the number of storage locations in memory needed to execute this algorithm is linear in n (if each entry of the input array fits into a single storage location).
-
While the information in the previous question is encouraging, it is still possible that the amount of storage space used by the Merge Sort algorithm could be reduced.
Consider both of the following variations of Merge Sort.
-
The values to be stored are given as the elements in a linked list, which can be treated as global data. Your recursive algorithm should receive a pointer or reference to the front element, as well as the length n of the list, as its inputs.
The algorithm should “sort” by reorganizing the links between the list elements, rather than making copies of entries.
-
The input array A and a second array B are both global data. For this version of the algorithm, the input should be a pair of integers i and j such that
0 ≤ i ≤ j < n
and such that the objective of the algorithm is to reorder the values stored in A, so that
A[i] ≤ A[i+1] ≤ … ≤ A[j].
The array B and at most a constant number of additional storage locations should be used by the algorithm to do this.
Write pseudocode for each of the above algorithms. If possible, describe the relationship between the worst-case running times and space requirements for these, and those of the original Merge Sort algorithm.
-
-
Write programs in Java implementing each of the above sorting algorithms that have been discussed. As usual you should try to make your algorithms as general as you can (by limiting any assumptions about the types of elements that are to be sorted, as much as you can).
If there is time, you should also consider writing programs for the alternative versions of the Merge Sort algorithm that are discussed in the previous question.
|
This page last modified:
http://www.cpsc.ucalgary.ca/~jacobs/cpsc331/F08/tutorials/tutorial11.html |