| Classical Sorting Algorithms |
About This Exercise
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, and Bubble Sort) that were presented during the lecture on classical sorting algorithms.
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;
Please read through and try to solve the problems on this exercise before attending the tutorial.
Expected Background
This exercise is based on material presented during the lecture on classical sorting algorithmis.
The Wikipedia pages on Selection Sort and Insertion Sort each include “algorithm animations” that show the behaviour of these algorithms in a way that might help some students to better understand the written descriptiosn of these algorithms.
Warmup Problems — To Check That You Understand the Basics
It is to be expected that all of the questions in this first section can be answered by any student who has successfully completed the prerequisites for this course, and attended the lecture in which classical sorting algorithms were discussed (reviewing the online lecture notes, as needed).
Students who do have difficulty with these questions should contact the course instructor to get extra help.
-
Give a brief description, in simple English, of each of the following sorting algorithms. Describe the worst-case (asymptotic) running time of each as well.
-
Consider the following array A.
Trace the execution of each of the sorting algorithms named in the above question when this array is supplied as input.
-
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?
To Be Discussed in the Tutorial
-
Give information about the running times of each of the “classical” sorting algorithms, when they are used to sort arrays of length n, by completing the following table.
Algorithm Best-Case Running Time Worst-Case Running Time Upper Bound Lower Bound Upper Bound Lower Bound Selection Sort Insertion Sort Bubble Sort -
Consider the following version of the Bubble Sort algorithm:
exchanges = true; while (exchanges) { exchanges = false; i = 0; while (i < A.length-1) { if (A[i] > A[i+1]) { Swap A[i] and A[i+1] exchanges = true; } i = i+1; } }
Compare and contrast this version of the “Bubble Sort” algorithm with the version that is presented in the lecture notes. How are they different? -
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, as this is described in the lecture notes.
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.
-
Finally, describe how you could modify the “Bubble Sort” algorithm so that its worst-case performance is not significantly worse than what it is now, but so that its best-case performance is much better.
|
Last updated:
http://www.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/W17/tutorials/tutorial12.html |