home page - news - syllabus - schedule - assignments - tutorials - tests - java - references - Mike Jacobson |
Tutorial 1 - Tutorial 2 - Tutorial 3 - Tutorial 4 - Tutorial 5 - Tutorial 6 - Tutorial 7 - Tutorial 8 - Tutorial 9 - Tutorial 10 - Tutorial 11 - Tutorial 12 - Tutorial 13 - Tutorial 14 - Tutorial 15 - Tutorial 16 - Tutorial 17 - Tutorial 18 - Tutorial 19 - Tutorial 20 - Tutorial 21 - Tutorial 22 - Tutorial 23 |
Classical Sorting Algorithms |
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
Please read through and try to solve the problems on this exercise before attending the tutorial.
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.
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?
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/W12/tutorials/tutorial15.html |