Due 4/5
Tree sort
Goals
The goals of this assignment are as follows:
- Practice writing code using binary search trees (dynamic structures).
- Practice writing code using recursion.
Overview
This homework is about sorting. You will implement the tree sort algorithm to help you learn about binary search trees (BSTs) and sorting algorithms.
There are no starter files.
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
Reminder: Do not copy this code or anything else into your code (unless marked as
"Okay to copy/adapt" by one of the instructors). However, you may run this in your account
by running
264get HW14
.
#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_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);
empty_bst(&bst);
// Demonstrate tree_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 tree_sort_array(array1)");
tree_sort_array(array1, size1);
_print_array(array1, size1, "After tree_sort_array(array1)");
return EXIT_SUCCESS;
}
/* vim: set tabstop=4 shiftwidth=4 fileencoding=utf-8 noexpandtab: */
Output
Before tree_sort_array(array1) 5 4 2 1 7 6 3 After tree_sort_array(array1) 1 2 3 4 5 6 7
Requirements
- Your submission must contain each of the following files, as specified:
- Whenever
size
==0,root
must be NULL. - Do not include helpers (if any) here.
-
Steps:
① call
create_bst(…)
, ② use in-order traversal to store sorted values inarray
(same memory), ③ callempty_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 callingcreate_bst(…)
; those must be freed before this function returns. size
is the number of elements inarray
.- When size==0 array must be NULL and vice versa.
- If size==0 then return a BST with the root set to NULL.
malloc(…)
may be called from a total of one place in this function and any it depends on.- Set
root
to NULL, andsize
to 0. free(…)
may be called from a total of one place in this function and any it depends on.- 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. - 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
assert.h assert
sorts.c
,test_sorts.c
stdio.h printf
,fprintf
,stdout
,FILE
test_sorts.c
stdlib.h malloc
,free
,NULL
,size_t
,EXIT_SUCCESS
,EXIT_FAILURE
sorts.c
,test_sorts.c
,sorts.h
- Submissions must meet the code quality standards and the policies on homework and academic integrity.
file | contents | |
---|---|---|
sorts.h | type definitions |
BST
struct type with 2 fields: root (BSTNode*) and size (int).
|
BSTNode
struct type with 3 fields: value (int), left , and right (BSTNode*)
|
||
function declarations |
one for each required function in your sorts.c
|
|
sorts.c | function definitions |
tree sort array(int✶ array, size t size)
→ return type: void
Sort array by creating a BST and then traversing it.
|
create bst(const int✶ array, int size)
→ return type: BST
Create a new BST .
|
||
empty bst(BST✶ a bst)
→ return type: void
Free all the nodes in the BST.
|
||
test_sorts.c | function definitions |
main(int argc, char✶ argv[])
→ return type: int
Test your functions in sorts.c.
|
expected.txt | functions | Expected output from running your test_sorts.c |
Submit
To submit HW14 from within your hw14 directory,
type
264submit HW14 sorts.h sorts.c test_sorts.c miniunit.h clog.h Makefile
Pre-tester ●
The pre-tester for HW14 has not yet been released. As soon as it is ready, this note will be changed.
Q&A
-
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- 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.
-
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.) - In the .h file (sorts.h), add an include guard.
- 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).
- Submit. Your code is nearly empty, but this gives you a backup.
make submit
(or264submit sorts.h sorts.c test_sorts.c miniunit.h clog.h Makefile
for Luddites). -
Decide on a general order in which to implement the various parts of
the assignment. For HW14, you could do the
three parts in any order. If you have no opinion, we lightly suggest
doing in this order:
①
tree_sort_array(…)
, ②quick_sort_array(…)
. But again, it's up to you. - In your test code file (test_sorts.c), create your first test.
- Write one very simple test (e.g., sort empty array). At this point, your sorts.c should have no useful code in it.
- Write just enough code in sorts.c to pass your easy test.
-
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. - Add a slightly harder test (e.g., sort array of size one).
- Add code to your sorts.c so that both of your tests should pass.
- Run your tests. Make any fixes so that both of your tests do pass.
-
Gradually add tests, extend implementation, run tests, and fix, until one
section of your project is complete (e.g., until
create_bst(…)
is working). - Follow the above steps to complete the rest of HW14.
- Re-read the specification—especially the Requirements table—and make sure you have done everything, and your types/fields/functions all match the specification.
-
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. -
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
-
Can I add helper functions to sorts.c?
Yes. Make sure the names begin with "_". -
Is there a warm-up?
No. -
Should I use recursion for the BST operations
(
create_bst(…)
,tree_sort_array(…)
, andempty_bst(…)
)?
Short answer: Yes.Long answer: All of these things can be accomplished without recursion, using onlywhile
loops. However, those methods are messier.The methods demonstrated in class (see snippets) use recursion, and that is what we recommend. -
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. -
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 HW14, this is all you need to know.Example:In theprint_bst(Node* root)
function in the snippet:- Print the left subtree by calling
print_bst(root -> left)
recursively. - Print the root by calling
printf("%d\n", root -> value)
. - 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):print_bst(root -> left)
has no effect.printf("%d ", root -> value)
prints 4 .print_bst(root -> right)
has no effect.
If the tree has three nodes (i.e., root has children but no grandchildren):print_bst(root -> left)
prints 2 .printf("%d ", root -> value)
prints 4 .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):print_bst(root -> left)
prints 1 2 3 .printf("%d ", root -> value)
prints 4 .print_bst(root -> right)
prints 5 6 7 .
Altogether, it prints 1 2 3 4 5 6 7 .Fortree_sort_array(…)
, you are following the same process, except instead of printing a value withprintf(…)
, you store it in the array. - Print the left subtree by calling
Updates
4/4/2022 |
|