Goals

Overview

This homework is about sorting. You will implement the queue sort and the tree sort algorithm to help you learn about structs in C along with binary search trees (BSTs) and sorting algorithms in general.

It is recommended you read the full overview before you start coding this assignment. The sections describe the data structures we will be using.

Stack

It is recommended you start by implementing print_list(…) as having a working print function will make debugging a lot easier. This function will use a function address similar to the one used in warmup.c.

After that, it is recommended to implementing the stack logic in stack_push(…) and stack_pop(…) next, as neither require using the compare function.

When a stack is implemented as a linked list, the object that is pushed onto the stack always appears as the first item on the list. Therefore, if we push the list of numbers 5, 10, 4, 3, 1 onto a stack successively, we have the following linked list:

1→3→4→10→5→NULL

If we pop from the stack, we have

3→4→10→5→NULL

7→3→4→10→5→NULL

You will also write a function to destroy a linked list and free all memory associated with it.

Priority Queue

A priority queue is implemented as a linked list where the objects stored in the list are actually ordered. For example, if we want to store a linked list of numbers 5, 10, 4, 3, 1, and the linked list is used to implement a priority queue, the linked list should appear as follows:

1→3→4→5→10→NULL

Here, we assume that "→" is the "pointer." We also assume that a smaller number has a higher priority, and it is therefore listed first. If we now want to get number 7 to join the priority queue, we should have the list updated to:

1→3→4→5→7→10→NULL

We call this the enqueue operation. To remove an item from a priority queue, we always remove the item with the highest priority. This is call the dequeue operation. In this case, a dequeue operation will remove 1 from the list:

3→4→5→7→10→NULL

Your implementation of a priority queue will be similar to the stack from the warmup. Unlike the stack, priority queues require sorting the elements as they are inserted.

Binary Search Tree

Unlike a linked list, each node in a binary search tree has two children, named the left and the right child. A binary search tree requires that all left children are smaller than the root, while all right children are larger than the root.

Similarly to the priority queue, the binary search tree is a sorted data structure. However, unlike the linked lists we will not be implementing logic to remove nodes from a binary search tree, only to add nodes and print the nodes.

Warm-up exercises

This assignment includes a warm-up exercise to help you get ready. This accounts for 10% of your score for HW12. Scoring will be relatively light, but the usual base requirements apply.

In the starter files, you will find a file called warmup.c. It contains three unfinished functions and a definition for the node sturct. The first function, called print_list(…), takes a linked list as the argument and will print each integer element, separated by commas and followed by a newline. The second, stack_push(…) will malloc(…) a node and insert it as the start of the linked list. The final, destroy_list(…), will free(…) the whole linked list.

Fill in the implementation of all 3 functions.

To test your warm-up exercise, type the following:

gcc -o warmup warmup.c
./warmup
valgrind ./warmup

The output should be similar to the following:

dburnet@ececomp1 ~/264/hw12
$ gcc -o warmup warmup.c

dburnet@ececomp1 ~/264/hw12
$ ./warmup
7
1, 7
5, 1, 7

dburnet@ececomp1 ~/264/hw12
$ valgrind ./warmup

==37134== Memcheck, a memory error detector
==37134== Copyright (C) 2002-2012, and GNU GPL'd, by Julian Seward et al.
==37134== Using Valgrind-3.8.1 and LibVEX; rerun with -h for copyright info
==37134== Command: ./warmup
==37134==
7
1, 7
5, 1, 7
==37134==
==37134== HEAP SUMMARY:
==37134==     in use at exit: 0 bytes in 0 blocks
==37134==   total heap usage: 3 allocs, 3 frees, 48 bytes allocated
==37134==
==37134== All heap blocks were freed -- no leaks are possible
==37134==
==37134== For counts of detected and suppressed errors, rerun with: -v
==37134== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

Opt out

In a hurry, and don't need the practice? This warm-up is here to help you learn what you need to succeed on the rest of this assignment—not to add additional work. Therefore, we give you an option. Those who feel that they do not need the practice may "opt out" by modifying warmup.c so that it does nothing but print the following message exactly and then exit:

I already know this and do not need to practice.

If you do that, then your score for HW12 will be based solely on the rest of this assignment. If you leave the warmup.c undone, if you do not turn in a warmup.c, or if the message it prints does not match perfectly, then you will receive 0 for the warmup portion of this assignment (10%).

Submission

The warm-up will be turned in together with the rest of HW12.

Outline of a solution

👌 Okay to copy/adapt anything you see in these two screenshot images. (You may not copy code from lecture or anywhere else.)

Demonstration

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "sorts.h"

void _print_array(int* array, size_t size, const char* title) {
  printf("%s\n", title);
  for(int i = 0; i < size; i++) {
    printf("%d ", array[i]);
  }
  printf("\n\n");
}

int main(int argc, char* argv[]) {
  // Demonstrate create_pq(…)
  PriorityQueue pq = create_pq((int[2]) { 4, 2 }, 2);
  assert(pq.head             != NULL && pq.head->value == 2);
  assert(pq.head->next       != NULL && pq.head->next->value == 4);
  assert(pq.head->next->next == NULL);
  destroy_pq(&pq);

  // Demonstrate queue_sort_array(…)
  int array1[] = { 5, 4, 2, 1, 7, 6, 3 };
  size_t size1 = sizeof(array1) / sizeof(*array1);  // # of elements
  _print_array(array1, size1, "Before queue_sort_array(array1)");
  pq_sort_array(array1, size1);
  _print_array(array1, size1, "After  queue_sort_array(array1)");

  // Demonstrate create_bst(…)
  BST bst = create_bst((int[7]) { 4, 2, 6, 1, 3, 5, 7 }, 7);
  assert(bst.root        != NULL && bst.root->value        == 4);
  assert(bst.root->left  != NULL && bst.root->left->value  == 2);
  assert(bst.root->right != NULL && bst.root->right->value == 6);
  destroy_bst(&bst);

  // Demonstrate tree_sort_array(…)
  int array2[] = { 5, 4, 2, 1, 7, 6, 3 };
  size_t size2 = sizeof(array2) / sizeof(*array2);  // # of elements
  _print_array(array2, size2, "Before tree_sort_array(array2)");
  tree_sort_array(array2, size2);
  _print_array(array2, size2, "After  tree_sort_array(array2)");

  return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */

Output

Before pq_sort_array(array1)
5 4 2 1 7 6 3 

After  pq_sort_array(array1)
1 2 3 4 5 6 7 

Before tree_sort_array(array2)
5 4 2 1 7 6 3 

After  tree_sort_array(array2)
1 2 3 4 5 6 7 

Requirements

Submit

To submit HW12 from within your hw12 directory, type 264submit HW12 sorts.h sorts.c test_sorts.c miniunit.h clog.h Makefile warmup.c

Pre-tester ●

The pre-tester for HW12 has been released and is ready to use.

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 miniunit.h clog.h Makefile warmup.c for Luddites).
   6. Decide on a general order in which to implement the various parts of the assignment. For HW12, you could do the three parts in any order. If you have no opinion, we lightly suggest doing in this order: ①create_pq(…), ②pq_sort_array(…), ③destroy_pq(…), ④create_bst(…), ⑤tree_sort_array(…). ⑥destroy_bst(…). 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 create_bst(…) is working).
   15. Follow the above steps to complete the rest of HW12.
   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. Should I use recursion for the BST operations (create_bst(…), tree_sort_array(…), and destroy_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.
4. 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.
5. What is “in-order traversal”?
   
   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 HW12, 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