URI CSC 212 logo URI CSC 212

Mergesort & Quicksort

Lab 16

On this page:
✔️ Motivation
✔️ Background Info
✔️ Your Task
✔️ Requirements
✔️ Handing in
✔️ Grade Breakdown

Motivation (Why are we doing this?)

This lab will help you solidify your understanding of mergesort and quicksort.

Background Info

This lab was designed by a fellow undergrad to solidify your understanding of quicksort and mergesort. There are embedded hints throughout the code, as well as links to additional resources. Please read his comments closely.

Please refer to the course material (slides and readings) as needed.

Your Task

Complete the implementation of the sorting algorithms in lab16.cpp. Pay attention to the hints in the code.

  1. Download the files below (it’s easiest if you right click and then choose download or save)

    lab16.h
    Contains the declaration of the lab you’ll be implementing. Do not alter any of the given function signatures. Curious about the static keyword? Read about it.
    lab16.cpp
    Contains the definition of the lab you’ll be implementing.
    test.cpp
    Contains some tests that should pass as soon as you finish your implementation. You should add your own test cases to this file.
    doctest.h
    The library we’ll be using for our own automated tester. There’s a ton of code in here so don’t worry too much about understanding everything it does– just know the library is extremely powerful and we’ll only be scratching the surface of everything it can do. Do not edit this file.
  2. Once you have downloaded all the files, inspect them. Ask questions if you have them.
  3. Create your own makefile to compile and run your program. Refer to Lab 3 as needed.
  4. Complete the implementation of mergesort and merge in lab16.cpp. Pay attention to the hints in the code. Refer to the course material (slides and readings) as needed.
  5. Add your own test cases and uncomment the respective test casees for the functions you just completed.
  6. Run, compile, and test your program by running make in your terminal, while in the directory all these files are located in.
  7. Complete the implementation of quicksort and partition in lab16.cpp. Pay attention to the hints in the code. Refer to the course material (slides and readings) as needed.
  8. Add your own test cases and uncomment the respective test casees for the functions you just completed.
  9. Run, compile, and test your program by running make in your terminal, while in the directory all these files are located in.
  10. Create a new file called analysis.txt determine and explain the time complexity of merge() and partition() in terms of low and high.

Requirements

Your submission will be tested and graded by an autograder, for this reason it cannot be stressed enough that your program must exactly follow the assignment specifications:

  1. All sorting functions work as expected.
  2. Big-O analysis of merge() and partition() correctly defined and explained (graded manually).

Handing in

To submit your solution to Gradescope, select all of the following files and use the drag and drop option:

Grade Breakdown

You must successfully meet requirements 1 through 2 in order to receive credit for this assignment.

To receive any credit at all, you must abide by our Collaboration and Academic Honesty Policy. Failure to do so may result in a failing grade in the class and/or further disciplinary action.

Assignment hints and template code brought to you by Evan Russell.