CS 161 Lab 14

Overview

This lab will cover:

Lab Assignment

You will need the following files:

Also, create a blank document called studentList.txt and import it into your project.

Bubble sort and insertion sort have been done for you, you will just work on merge sort and analyae the running time of the different sorting algorithms.

Merge Sort

While sorting algorithms such as insertion, selection, or bubble sort work well enough for small amounts of data, they too slow for large data sets. Merge sort is a more efficient sorting algorithm that follows a fairly intuitive recursive process.

Given a list of items to sort, merge sort recursively divides the list into halves until the sublists are sufficiently small (for our purposes, this is size 1). Conceptually, you may imagine merge sort as creating a branching tree structure of lists. Once the size threshold is reached, sublists are then recursively merged in pairs to form a new list that is in sorted order. This is achieved by incrementally adding the smallest item from the heads of the two lists. Since the merge process is recursive, each sublist is independently in sorted order and can thus be easily merged by simply looking at the two leading elements.

Here is an example of merge sort in action (from Wikipedia):

Example of merge sort's recursively dividing a list into sublists of size 1. Sublists are then recursively merged in sorted order until a single list remains. This final list is in sorted order.

Your task is to merge sort an ArrayList of Student objects. You can compare objects with one another using Student.compareTo(Student other), which you must implement. The way that they will be sorted is exactly like last time, first by graduate level (undergrads go first), then by GPA (lowest to highest), then by name (A to Z).

Steps/tips for mergesort: 1. If the array does not meet the base case (which is what, looking at the picture), split it into two arrays, with the first half in one array and the second half in the other.
2. If you called the left array left then assign left to what sort(left) returns. Do the same thing for right.
3. Call merge on the two halves.
4. In merge, you take in two arrays, each of them are sorted in their own arrays, but you need to now put these two arrays into one sorted array.
5. A few counters will be needed, one to keep track of where you are in one array, the other to keep track of where you are in the other.

6. Also, you can first check to see if either of your counters for the two separate arrays are equal to their respective lengths. If so, add the rest of the contents of the other array to new array that we are returning.
You will see that with the current amount of students (we start with 100), then running times aren't that drastically different. Try throwing another for loop around the one by uncommenting the one that is there. This will multiply the number of students added to the file by 100.

If you need to make sure that mergesort is printing correctly, just uncomment the printArray() method in main.

As always, just ask if you need clarification on anything.