COMP 2210 Lab 6: Sorting solution

$25.00

Original Work ?
Category: You will Instantly receive a download link for .ZIP solution file upon Payment
Share This

Description

5/5 - (2 votes)

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

  1. 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.)
  2. Create the lab06 directory.
  3. Download the zip file associated with this lab, store it in the COMP2210/labs/lab06 directory, and unzip the file.
  4. 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.

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

  1. Open Sorts.java in jGRASP and compile it.
  2. Click on the Run in Canvas button  in the toolbar.
  3. In the “Choose Canvas File” dialog that opens, select Sorts.selection_sort.jgrasp_canvas.xml and click Ok.
  4. If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
  5. Click on the step-over button  in the Canvas window’s toolbar until the statement st.selectionSort(a); is highlighted.
  6. 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.
  7. 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.
  8. Click on the statement swap(a, i, min); so that the cursor is somewhere on this line.
  9. Predict what the value of min will be once execution reaches this statement.
  10. Click on the Run to Cursor button  in the Canvas toolbar and use the Canvas to confirm your prediction.
  11. Continue to interact with the Canvas until you feel as though you have a solid understanding of selection sort.
  12. 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.
  13. Close the Canvas window.

Insertion sort

  1. Open Sorts.java in jGRASP and compile it.
  2. Click on the Run in Canvas button  in the toolbar.
  3. In the “Choose Canvas File” dialog that opens, select Sorts.insertion_sort.jgrasp_canvas.xml and click Ok.
  4. If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
  5. Click on the step-over button  in the Canvas window’s toolbar until the statement st.insertionSort(a); is highlighted.
  6. 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.
  7. 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.
  8. Make sure you can predict what value j will have when the statement break; will execute next.
  9. Continue to interact with the Canvas until you feel as though you have a solid understanding of insertion sort.
  10. 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.
  11. Close the Canvas window.

Quicksort

  1. Open Sorts.java in jGRASP and compile it.
  2. Click on the Run in Canvas button  in the toolbar.
  3. In the “Choose Canvas File” dialog that opens, select Sorts.quicksort.jgrasp_canvas.xml and click Ok.
  4. If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
  5. Click on the step-over button  in the Canvas window’s toolbar until the statement st.quicksort(a); is highlighted.
  6. 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.
  7. Step-over  the shuffle(a); statement and pause when the quick(a, 0, a.length - 1); statement is highlighted.
  8. Step-in  to the call to quick.
  9. Step-over  the if statement and pause when the call to partitionOnPivot is highlighted.
    • This method will partition the array a around the given pivot value, which is designated in this call as a[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.
  10. 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.
  11. 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 sort a[lo] through a[j-1].
  12. Step-over  the first call to quick and see the effect reflected in the Canvas.
  13. The second recursive call to quick will sort the right half of the array; that is, it will sort a[j+1] through a[hi]. (Remember that a[j] holds the pivot and it’s already in the correct sorted position.)
  14. Step-over  the second call to quick and see the effect reflected in the Canvas.
  15. 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.
  16. 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.
  17. 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.

  1. Open Sorts.java in jGRASP and compile it.
  2. Click on the Run in Canvas button  in the toolbar.
  3. In the “Choose Canvas File” dialog that opens, select Sorts.quicksort.jgrasp_canvas.xml and click Ok.
  4. If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
  5. 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.
  6. Step-in  to the call to partitionOnPivot.
  7. Step-over  the statements in partitionOnPivot and observe their behavior in the Canvas window.
  8. 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.
  9. 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.
  10. 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.
  11. Close the Canvas window.

Merge sort

  1. Open Sorts.java in jGRASP and compile it.
  2. Click on the Run in Canvas button  in the toolbar.
  3. In the “Choose Canvas File” dialog that opens, select Sorts.merge_sort.jgrasp_canvas.xml and click Ok.
  4. If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
  5. Click on the step-over button  in the Canvas window’s toolbar until the statement st.mergesort(a); is highlighted.
  6. 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.
  7. Step-over  the statements of mergesort until msort(a, 0, a.length - 1);.{java} is highlighted.
  8. Step-in  to the call to msort.
  9. Step-over  the statements of msort and observe their effects in the Canvas window.
  10. 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.
  11. 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.
  12. 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.

  1. Open Sorts.java in jGRASP and compile it.
  2. Click on the Run in Canvas button  in the toolbar.
  3. In the “Choose Canvas File” dialog that opens, select Sorts.merge_sort.jgrasp_canvas.xml and click Ok.
  4. If necessary, resize the Canvas window that opens to make sure it fits on your screen appropriately.
  5. Click on the step-over button  in the Canvas window’s toolbar until the statement st.merge(a, lo, mid, hi); is highlighted.
  6. Step-in  to the call to merge.
  7. Step-over  the statements in partitionOnPivot and observe their behavior in the Canvas window.
  8. 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.
  9. 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.
  10. 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.
  11. Close the Canvas window.

Related products