Goals

Overview

In this assignment, you will implement the merge sort algorithm for linked lists. To add some perspective, you will also implement a tree sort (based on binary search trees) and write a wrapper function for the standard qsort(…) function, an implementation of the quicksort algorithm. However, the main focus on merge sort and linked lists.

There are no starter files.

About Merge Sort

// Credit: Wikipedia user 'Swfung8', License: CC BY-SA

Recursion is an elegant method for solving many problems. At first it can seem unnatural; however, it is actually very simple once you are used to it. The key thing to understand is that recursive programming has two steps:

1. A base case which is trivial.
2. A recursive case where you write the solution for the larger case in terms of the solution to smaller cases.

What makes (2) easy is that you simply assume that you have the solution of a smaller case. Life does not generally let you assume you have a solution that you have not yet found; however, if you think about it, it should be obvious (by induction) that recursion works this way.

In this assignment, we will use (1) and (2) above to sort linked-lists of integers using the "merge-sort" algorithm. Merge-sort is a beautiful algorithm that sorts extremely quickly with large inputs. It is also the best possible algorithm to use for sorting linked-lists.

Merge sort works as follows:

1. Base case:
   You never need to sort a list of length 0 or 1; it is already "sorted", so-to-speak. To implement the base case, simply return the input list if its length is 0 or 1. (In general, base cases are trivial like this.)
2. Recursive case:
   Lets wave our hand, and assume that we know how to sort smaller lists already. (See, recursion is easy.) For the recursive case, we do the following:
   1. Divide the list into two smaller lists of equal size, +/- one node.
   2. Recursively sort each of the two smaller lists. (Wow: easy.)
   3. You now have two small lists that are sorted. To produce the final large sorted list, you "merge" the two smaller lists together.
      1. Create a brand new empty list, which will be the result-list.
      2. While both small lists are non-empty, look at the head node of each. Take the smaller head node off of the front of its list, and append it to the result-list.
      3. Eventually one (or perhaps both) of the smaller lists will be empty. At this stage, append the non-empty list (if there is one) onto the end of the result-list.

// Credit: Aaron Michaux, Prof. Yung-Hsiang Lu … This description adapted from a previous ECE 264 assignment

Requirements

Submit

To submit HW07, type 264submit HW07 sorts.h sorts.c test_sorts.c expected.txt from inside your hw07 directory.

Pre-tester ●

The pre-tester for HW07 has not yet been released. As soon as it is ready, this note will be changed.

Q&A

1. Where's the starter code? How am I supposed to start?
   Learning to program in C entails learning to set up your files and code your project to meet a specification—without being given step-by-step instructions. That said, here is a general process you can use for doing that.
   How to do any coding homework in ECE 264
   1. First, identify the files you are responsible for producing. In this case, there are four files: sorts.c, sorts.h, test_sorts.c, and expected.txt. Create an (almost) empty file for each.
   2. In the .c and .h files, add a Vim modeline. (Tip: In Vim on ecegrid, type newc and press Tab to get a skeleton file, including the modeline. Remove any #include statements or anything else that isn't needed or allowed.)
   3. In the .h file (sorts.h), add an include guard.
   4. Create your makefile. This is optional, but recommended. You do not need to use miniunit.h or clog.c in order to use make (but you may if you wish).
   5. Submit. Your code is nearly empty, but this gives you a backup.
      make submit (or 264submit sorts.h sorts.c test_sorts.c expected.txt for Luddites).
   6. Decide on a general order in which to implement the various parts of the assignment. For HW07, you could do the three parts in any order. If you have no opinion, we lightly suggest doing in this order: ① merge_sort_array(…), ②tree_sort_array(…), ③ quick_sort_array(…). But again, it's up to you.
   7. In your test code file (test_sorts.c), create your first test.
   8. Write one very simple test (e.g., sort empty array). At this point, your sorts.c should have no useful code in it.
   9. Write just enough code in sorts.c to pass your easy test.
   10. Run your test (e.g., make test (or ./test_sorts for Luddites). Hopefully, your simple test passes. This step is to test the mechanics of your testing, and verify that you have the correct function signatures and such.
   11. Add a slightly harder test (e.g., sort array of size one).
   12. Add code to your sorts.c so that both of your tests should pass.
   13. Run your tests. Make any fixes so that both of your tests do pass.
   14. Gradually add tests, extend implementation, run tests, and fix, until one section of your project is complete (e.g., until merge_sort_array(…) is working).
   15. Follow the above steps to complete the rest of HW07.
   16. Re-read the specification—especially the Requirements table—and make sure you have done everything, and your types/fields/functions all match the specification.
   17. Check for gaps in your tests. Make sure you get 100% line coverage from make coverage. This is no guarantee of perfection, but if you don't have 100% coverage, you need to fix that. Make sure your tests cause every part of your implementation code to be executed.
   18. Think through your tests carefully. Make sure you have covered all:
       • “edge cases” – extreme values
       • “corner cases” – values that cause your code to behave differently
       • “special cases” – exceptions to normal functionality described in the specification
       • "easy cases" – easy for you to understand
       (Note: These are not standard terms.)
2. Can I add helper functions to sorts.c?
   Yes. Make sure the names begin with "_".
3. Is there a warm-up?
   No.
4. Is it a violation of the spec if qsort(…) calls malloc(…)?
   No. The only requirement is that your code not call malloc(…) as a result of calling quick_sort_array(…).
5. Should I use recursion for the BST operations (create_bst(…), tree_sort_array(…), and empty_bst(…))?
   
   Short answer: Yes.
   Long answer: All of these things can be accomplished without recursion, using only while loops. However, those methods are messier.
   The methods demonstrated in class (see snippets) use recursion, and that is what we recommend.
6. How do I create a BST? … delete a BST?
   
   To create a BST, start with an empty BST (root = NULL) and then insert each element you wish to add.
   To delete a BST, delete the left and right subtree (recursively). Then, free the root.
   The bst.c snippet from 2/21/2019 illustrates everything you need to do. You may not copy that snippet, but once you understand it, you should have no trouble doing what you need to do with BSTs for HW07.
7. What is “in-order traversal”?
   
   That is just a fancy name for the method of printing a BST shown in the snippet from 2/21/2019.
   With in-order traversal means you “visit” (i.e., do something with) the left subtree, then the root, and finally the right subtree. In that example, “visit” meant printing the value of a node. For a BST, this results in printing the values in order.
   You will learn a bit more about tree traversals later, but for HW07, this is all you need to know.
   Example:
   In the print_bst(Node* root) function in the snippet:

   1. Print the left subtree by calling print_bst(root -> left)recursively.
   2. Print the root by calling printf("%d\n", root -> value).
   3. Print the right subtree by calling print_bst(root -> right)recursively.
   If the tree has zero nodes (i.e., empty), we do nothing.
   

   If the tree has one node (i.e., root has no children):

   1. print_bst(root -> left) has no effect.
   2. printf("%d ", root -> value) prints 4 .
   3. print_bst(root -> right) has no effect.
   

   If the tree has three nodes (i.e., root has children but no grandchildren):

   1. print_bst(root -> left) prints 2 .
   2. printf("%d ", root -> value) prints 4 .
   3. print_bst(root -> right) prints 6 .

   Altogether, it prints 2 4 6 .
   

   If the tree has seven nodes (i.e., root has children but no grandchildren):

   1. print_bst(root -> left) prints 1 2 3 .
   2. printf("%d ", root -> value) prints 4 .
   3. print_bst(root -> right) prints 5 6 7 .

   Altogether, it prints 1 2 3 4 5 6 7 .
   For tree_sort_array(…), you are following the same process, except instead of printing a value with printf(…), you store it in the array.

Updates