Due 11/8

Sorting

Goals

The goals of this assignment are as follows:

Practice writing code using linked lists and binary search trees (dynamic structures).
Practice writing code using recursion.
Learn to use function addresses (function pointers).
Learn to use the qsort(…) function.
Gain some perspective on different sorting algorithms.

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.

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:

A base case which is trivial.
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:

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.)
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

Your submission must contain each of the following files, as specified:

file	contents
sorts.h	type definitions	List struct type with 3 fields: `head` (ListNode), `tail` (ListNode) and `size` (int) Whenever `size`==0, `head` and `tail` must be NULL.
		ListNode struct type with 2 fields: `value`(int), `next` (ListNode*)
		BST struct type with 2 fields: `root` (BSTNode*) and `size` (int). Whenever `size`==0, `root` must be NULL.
		BSTNode struct type with 3 fields: `value`(int), `left`, and `right` (BSTNode*)
	function declarations	one for each required function in your sorts.c Do not include helpers (if any) here.
sorts.c	function definitions	`merge sort array(int✶ array, size t size)` → return type: void Sort `array` using `merge_sort_list(…)`. Do not merge sort the array directly. This must use your `merge_sort_list(…)`. Store the result in the same array that was passed in. Steps: ① call `create_list(…)`, ② call `merge_sort_list(…)`, ③ store the sorted values in `array` (same memory), ④ call `empty_list(…)`. The purpose is to make `merge_sort_list(…)` comparable with the other sort functions. This may not result in any heap allocation (i.e., calls to `malloc(…)`), except for the list nodes allocated as a result of calling `create_list(…)`; those must be freed before this function returns.
		`tree sort array(int✶ array, size t size)` → return type: void Sort `array` by creating a BST and then traversing it. Steps: ① call `create_bst(…)`, ② use in-order traversal to store sorted values in `array` (same memory), ③ call `empty_bst(…)`. Store the result in the same array that was passed in. This may not result in any heap allocation (i.e., calls to `malloc(…)`), except for the BST nodes allocated as a result of calling `create_bst(…)`; those must be freed before this function returns.
		`quick sort array(int✶ array, size t size)` → return type: void Sort `array` using the `qsort(…)` standard library function. This should simply call the `qsort(…)` library function. The `qsort(…)` function requires the use of function addresses (function pointers). This may not result in any heap allocation (i.e., calls to `malloc(…)`) by your code. Yes, this is easy, but make sure you understand how it works!
		`create list(const int✶ array, int size)` → return type: List Create a new `List`. `size` is the number of elements in `array`. When size==0 array must be NULL and vice versa. If size==0 then return a list with the head and tail set to NULL. `malloc(…)` may be called from a total of one place in this function and any it depends on.
		`merge sort list(List✶ list)` → return type: void Merge sort `list`. This may not result in any heap allocation (i.e., calls to `malloc(…)`).
		`empty list(List✶ list)` → return type: void Free all the nodes in the list. Set `head` and `tail` to NULL, and `size` to 0. `free(…)` may be called from a total of one place in this function and any it depends on.
		`create bst(const int✶ array, int size)` → return type: BST Create a new `BST`. `size` is the number of elements in `array`. When size==0 array must be NULL and vice versa. If size==0 then return a BST with the root set to NULL. This can be a slight modification of your `create_bst_of_int(…)` from the HW11 warm-up. `malloc(…)` may be called from a total of one place in this function and any it depends on.
		`empty bst(BST✶ bst)` → return type: void Free all the nodes in the BST. Set `root` to NULL, and `size` to 0. This can be a slight modification of `destroy_bst_of_int(…)` from the HW11 warm-up. `free(…)` may be called from a total of one place in this function and any it depends on.
test_sorts.c	function definitions	`main(int argc, char✶ argv[])` → return type: int Test your functions in sorts.c. This must cause every line of code in your sorts.c to be executed. Every public function in sorts.c must be called directly from `main(…)` and/or from a helper within test_sorts.c.
expected.txt	functions	Expected output from running your test_sorts.c

Use the typedef syntax to declare all struct types.

Only the following externally defined functions and constants are allowed in your .c files. (You may put the corresponding #include <…> statements in the .c file or in your sorts.h, at your option.)

header	functions/symbols	allowed in…
stdbool.h	`bool`, `true`, `false`	`sorts.c`, `sorts.h`, `test_sorts.c`
stdio.h	`printf`, `fprintf`, `stdout`, `FILE`	`test_sorts.c`
stdlib.h	`malloc`, `free`, `NULL`, `EXIT_SUCCESS`, `EXIT_FAILURE`	`sorts.c`, `test_sorts.c`, `sorts.h`
assert.h	`assert`	`sorts.c`, `test_sorts.c`

Feel free to suggest additional header files or functions that you would like to use.

Submissions must meet the code quality standards and the policies on homework and academic integrity.

A bonus assignment might be added to this sometime before the weekend.

How much work is this?

This is intended to be a similar amount of effort to HW11, but your mileage may vary.

As usual… Programming with dynamic memory usually entails some time debugging. Allow time for that.

Q&A

Can I reuse code from HW11?
Yes.
Can I add helper functions to sorts.c?
Yes. Make sure the names begin with "_".
Is there a warm-up?
No.
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(…).

Updates

11/5/2016	Added Q4 and related not to spec under `quick_sort_array(…)`
11/6/2016	Change: expected.txt is required
11/7/2016	Correction: In `BST` when `size`==0 `root` should be NULL.
11/13/2016	Added boilerplate reminder about code quality standards and policies. It had been inadvertently omitted. Syllabus already states these apply to every assignment but we try to put a reminder in every assignment.

Advanced C Programming

Autumn 2016 :: ECE 264 :: Purdue University