Description
This lab focuses on four common sorting algorithms and sample implementations. After completing this lab you should
- Understand the selection sort algorithm.
- Understand an implementation of selection sort in a Java method.
- Understand the insertion sort algorithm.
- Understand an implementation of insertion sort in a Java method.
- Understand the merge sort algorithm.
- Understand an implementation of merge sort in a Java method.
(This document is available outside of Canvas here.)
Set-up
- Open the
COMP2210/labs
directory on your Engineering H: drive. (If you didn’t complete the previous lab where you created this directory structure, do so now.) - Create the
lab06
directory. - Download the zip file associated with this lab, store it in the
COMP2210/labs/lab06
directory, and unzip the file. - Open jGRASP to the
lab06
directory.
Watching sorts work
Sorting was the subject of one of the first attempts at software visualization (see Ron Baecker’s Sorting Out Sorting from 1981). The behavior of sorting algorithms lends itself well to a visual depiction, so canned animations of sorting remain popular. Below are three good examples.
http://www.sorting-algorithms.com/
http://visualgo.net/sorting.html
https://www.cs.usfca.edu/~galles/visualization/ComparisonSort.html
By using jGRASP and taking advantage of its Viewer Canvas you can get the advantages of algorithm animations in the context of your own code. The Sorts.java
file contains implementations of all the sorting algorithms discussed in lecture. The XML files are jGRASP Canvas files – layout specification and other settings for pre-configured visualizations of each of the four main sorts.
The following sections can be done in any sequence. The instructions are written so that each section is self contained.
Selection sort
- Open
Sorts.java
in jGRASP and compile it. - Click on the Run in Canvas button
in the toolbar.
- In the “Choose Canvas File” dialog that opens, select
Sorts.selection_sort.jgrasp_canvas.xml
and click Ok. - If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
- Click on the step-over button
in the Canvas window’s toolbar until the statement
st.selectionSort(a);
is highlighted. - Click on the step-in button
in the Canvas window’s toolbar. Note that the viewers on the Canvas “light up” with their current values.
- Step-over
each statement and observe its effect in the Canvas. Continue to do this until you get a good sense of the behavior of this method.
- Click on the statement
swap(a, i, min);
so that the cursor is somewhere on this line. - Predict what the value of
min
will be once execution reaches this statement. - Click on the Run to Cursor button
in the Canvas toolbar and use the Canvas to confirm your prediction.
- Continue to interact with the Canvas until you feel as though you have a solid understanding of selection sort.
- Click on the “End” button in the jGRASP Run I/O controls at the bottom of the jGRASP desktop to stop the debugger from running.
- Close the Canvas window.
Insertion sort
- Open
Sorts.java
in jGRASP and compile it. - Click on the Run in Canvas button
in the toolbar.
- In the “Choose Canvas File” dialog that opens, select
Sorts.insertion_sort.jgrasp_canvas.xml
and click Ok. - If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
- Click on the step-over button
in the Canvas window’s toolbar until the statement
st.insertionSort(a);
is highlighted. - Click on the step-in button
in the Canvas window’s toolbar. Note that the viewers on the Canvas “light up” with their current values.
- Step-over
each statement and observe its effect in the Canvas. Continue to do this until you get a good sense of the behavior of this method.
- Make sure you can predict what value
j
will have when the statementbreak;
will execute next. - Continue to interact with the Canvas until you feel as though you have a solid understanding of insertion sort.
- Click on the “End” button in the jGRASP Run I/O controls at the bottom of the jGRASP desktop to stop the debugger from running.
- Close the Canvas window.
Quicksort
- Open
Sorts.java
in jGRASP and compile it. - Click on the Run in Canvas button
in the toolbar.
- In the “Choose Canvas File” dialog that opens, select
Sorts.quicksort.jgrasp_canvas.xml
and click Ok. - If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
- Click on the step-over button
in the Canvas window’s toolbar until the statement
st.quicksort(a);
is highlighted. - Click on the step-in button
in the Canvas window’s toolbar. Note that the viewers on the Canvas “light up” with their current values.
- Step-over
the
shuffle(a);
statement and pause when thequick(a, 0, a.length - 1);
statement is highlighted. - Step-in
to the call to
quick
. - Step-over
the
if
statement and pause when the call topartitionOnPivot
is highlighted.- This method will partition the array
a
around the given pivot value, which is designated in this call asa[lo]
. - Look at the Canvas to see what the pivot value will be and predict what the array will look like after the partioning is performed.
- This method will partition the array
- Step-over
the call to
partitionOnPivot
and confirm your prediction with the Canvas. Note that the pivot value is now in its final sorted position. - At this point the debugger is stopped on the first of two recursive calls to
quick
. This first call will recursively apply this process to the left half of the array; that is, it will sorta[lo]
througha[j-1]
. - Step-over
the first call to
quick
and see the effect reflected in the Canvas. - The second recursive call to
quick
will sort the right half of the array; that is, it will sorta[j+1]
througha[hi]
. (Remember thata[j]
holds the pivot and it’s already in the correct sorted position.) - Step-over
the second call to
quick
and see the effect reflected in the Canvas. - Continue to interact with the Canvas until you feel as though you have a solid understanding of quicksort.
- We will revisit this algorithm at the point in the course where we more fully cover recursion. But, if you’re interested, you can step-in
to the recursive calls and watch the entire sorting process occur step by step.
- We will revisit this algorithm at the point in the course where we more fully cover recursion. But, if you’re interested, you can step-in
- Click on the “End” button in the jGRASP Run I/O controls at the bottom of the jGRASP desktop to stop the debugger from running.
- Close the Canvas window.
Partition
The actual work of rearranging elements of the array in quicksort is accomplished by partitioning array elements around a pivot value. It’s important that you understand this process in detail.
- Open
Sorts.java
in jGRASP and compile it. - Click on the Run in Canvas button
in the toolbar.
- In the “Choose Canvas File” dialog that opens, select
Sorts.quicksort.jgrasp_canvas.xml
and click Ok. - If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
- Click on the step-over button
in the Canvas window’s toolbar until the statement
st.partitionOnPivot(a, 0, a.length - 1, 5);
is highlighted. - Step-in
to the call to
partitionOnPivot
. - Step-over
the statements in
partitionOnPivot
and observe their behavior in the Canvas window. - After you have observed the method’s execution to completion, change the last parameter to
partitionOnPivot
to a different value and repeat all the steps above. - Continue to experiment with different choices of the pivot value until you are confident that you understand both the purpose of this method and the manner in which it accomplishes this purpose.
- Click on the “End” button in the jGRASP Run I/O controls at the bottom of the jGRASP desktop to stop the debugger from running.
- Close the Canvas window.
Merge sort
- Open
Sorts.java
in jGRASP and compile it. - Click on the Run in Canvas button
in the toolbar.
- In the “Choose Canvas File” dialog that opens, select
Sorts.merge_sort.jgrasp_canvas.xml
and click Ok. - If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
- Click on the step-over button
in the Canvas window’s toolbar until the statement
st.mergesort(a);
is highlighted. - Click on the step-in button
in the Canvas window’s toolbar. Note that the viewers on the Canvas “light up” with their current values.
- Step-over
the statements of
mergesort
untilmsort(a, 0, a.length - 1);
.{java} is highlighted. - Step-in
to the call to
msort
. - Step-over
the statements of
msort
and observe their effects in the Canvas window. - Continue to interact with the Canvas until you feel as though you have a solid understanding of merge sort.
- We will revisit this algorithm at the point in the course where we more fully cover recursion. But, if you’re interested, you can step-in
to the recursive calls and watch the entire sorting process occur step by step.
- We will revisit this algorithm at the point in the course where we more fully cover recursion. But, if you’re interested, you can step-in
- Click on the “End” button in the jGRASP Run I/O controls at the bottom of the jGRASP desktop to stop the debugger from running.
- Close the Canvas window.
Merge
The actual work of rearranging elements of the array in merge sort is accomplished by merging elements from two sorted halves of an array into another array. It’s important that you understand this process in detail.
- Open
Sorts.java
in jGRASP and compile it. - Click on the Run in Canvas button
in the toolbar.
- In the “Choose Canvas File” dialog that opens, select
Sorts.merge_sort.jgrasp_canvas.xml
and click Ok. - If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
- Click on the step-over button
in the Canvas window’s toolbar until the statement
st.merge(a, lo, mid, hi);
is highlighted. - Step-in
to the call to
merge
. - Step-over
the statements in
partitionOnPivot
and observe their behavior in the Canvas window. - After you have observed the method’s execution to completion, change the values in the array parameter to
merge
and repeat all the steps above. - Continue to experiment with different arrangements of the values in the array until you are confident that you understand both the purpose of this method and the manner in which it accomplishes this purpose.
- Click on the “End” button in the jGRASP Run I/O controls at the bottom of the jGRASP desktop to stop the debugger from running.
- Close the Canvas window.