Algorithms and OOD (CSC 207 2013F) : Labs
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Summary: We explore the construction of Quicksort.
Prerequisite Knowledge: The general structure of Quicksort. Arrays. Loop invariants.
Fork and clone the repository at https://github.com/Grinnell-CSC207/sorting
a. Explain why there are two sorting procedures in
Quicksort.java
, one called sorti
and one
called qsort
.
b. The Quicksort algorithm says (approximately): “Divide the
collection into small values and large values, sort the two
subcollections, and join them back together.” How is each
aspect of that algorithm represented in qsort
?
c. In your own words, explain what value partition
returns.
Quicksort requires you to pick an element of the collection as a “pivot” to use to identify small (<= pivot) and large (> pivot) elements. Write a procedure that, given an array, a lower bound, and an upper bound, and a comparator, picks a random pivot in the given range. (You probably won't need the comparator, but we include it because we'll use it later.)
Sketch a loop invariant for partition. (You may want to refer to the reading for a suggestion. If you use that suggestion, you should make sure that you understand what's going on.
You should now be ready to implement the partition method. Do so.
Conduct a few tests or experiments to determine whether your partition and sorting methods work correctly.
We can significantly improve Quicksort by randomly picking three candidates for the pivot, and using the median of the three. Rewrite your procedure to pick a Pivot to use that strategy.
Primary: [Front Door] [Schedule] - [Academic Honesty] [Disabilities] [Email] [FAQ] [IRC] [Teaching & Learning]
Current: [Assignment] [EBoard] [Lab] [Outline] [Partners] [Reading]
Sections: [Assignments] [EBoards] [Examples] [Handouts] [Labs] [Outlines] [Partners] [Readings]
Reference: [Java 7 API] [Java Code Conventions]
Related Courses: [CSC 152 2006S (Rebelsky)] [CSC 207 2013S (Walker)] [CSC 207 2011S (Weinman)]
Misc: [SamR] [Glimmer Labs] [CS@Grinnell] [Grinnell] [Issue Tracker (Course)] [Issue Tracker (Textbook)]
Copyright (c) 2013 Samuel A. Rebelsky.
This work is licensed under a Creative Commons Attribution 3.0 Unported License. To view a copy of this
license, visit http://creativecommons.org/licenses/by/3.0/
or send a letter to Creative Commons, 543 Howard Street, 5th Floor,
San Francisco, California, 94105, USA.