Homework 10 - james-bern/CS136 GitHub Wiki
For an array/list with
- time complexity is how long an algorithm takes to run
-
space complexity is how much extra space an algorithm takes to run (the input array does NOT count)
- if the algorithm is in-place (just uses swaps) then it is
$O(1)$ space - if we had to build a work array of
$n$ elements then it is$O(n)$ space
- if the algorithm is in-place (just uses swaps) then it is
In this lab, you will get a feel for sorting and searching by implementing some little functions.
- To search an array/list means to find a value in it (and return its index; return
-1if not there). - To sort an array/list means to rearrange its elements so they are in ascending order (get bigger from left to right.)
The lab will crescendo in two sorting algorithms that work by building data structures.
- To do tree sort...
- Build a binary search tree (sorted binary tree).
- Traverse it to read out the elements in sorted order (and store them in an array/list).
- To do heapsort...
- Build an (implicit) max binary heap.
- Repeatedly remove the largest element to build up a sorted array.
- Recall that the max heap interface's
remove()function removes and returns the max (largest) element in the heap.
- Recall that the max heap interface's
-
To get a B:
- ✅ Implement and document (fill in the time space complexities of) all the functions other than
treeSortandheapSort.
- ✅ Implement and document (fill in the time space complexities of) all the functions other than
-
To get a A:
- ✅ Implement and document (explicit)
treeSort.
- ✅ Implement and document (explicit)
-
To get an S:
- ✅ All of the above.
- ✅ Do 1+ of...
- ✅ (Highly Recommended) Implement and document implicit
heapSort.‼️ Make sure you have the currentheapSortStarter Code! Check the Starter Code at the bottom to be sure!- ✨ https://en.wikipedia.org/wiki/Heap_%28data_structure%29
- ✨ https://en.wikipedia.org/wiki/Heapsort
- ✨ You will want helper "indexing functions" like
int parent(int i) { return (i - 1) / 2; }int leftChild(int i) { ... }int rightChild(int i) { ... }
- ✅ Using
Cow.javacreate a maze generator that uses some sort of (randomized) depth first traversal.
- ✅ (Highly Recommended) Implement and document implicit
- ✅ Put the output of
runAutograder()in a comment at the top of your code file.- 🚨 You must do this.
import java.util.*;
class HW10 {
static void runAutograder() {
// indices 0 1 2 3 4 5 6 7
int[] U = { 9, 4, 0, 1, 7, 6, 8, 3 }; // Unsorted
int[] S = { 0, 1, 3, 4, 6, 7, 8, 9 }; // Sorted
int[] L = { 0, 1, 3, 4, 6, 7, 8 }; // different Length
int[] V = { 0, 1, 3, 4, 5, 7, 8, 9 }; // different Values
int[] O = { 0 }; // One element
int[] E = {}; // Empty
System.out.println("NOTE: Many of the tests assume your areEqual(...) implementation is perfect.");
System.out.println("\nRUNNING AUTOGRADER");
System.out.print ("------------------");
System.out.print("\nareEqual");
_grade(areEqual(S, S.clone()) == true);
_grade(areEqual(S, U) == false);
_grade(areEqual(S, V) == false);
_grade(areEqual(S, L) == false);
_grade(areEqual(S, E) == false);
_grade(areEqual(E, E) == true);
System.out.print("\nisSorted");
_grade(isSorted(S) == true);
_grade(isSorted(U) == false);
_grade(isSorted(O) == true);
_grade(isSorted(E) == true);
System.out.print("\nlinearSearch");
_grade(linearSearch(S, 0) == 0);
_grade(linearSearch(S, 6) == 4);
_grade(linearSearch(S, 9) == 7);
_grade(linearSearch(S, 5) == -1);
_grade(linearSearch(S, -10) == -1);
_grade(linearSearch(O, 0) == 0);
_grade(linearSearch(O, 5) == -1);
_grade(linearSearch(E, 5) == -1);
_grade(linearSearch(U, 9) == 0);
System.out.print("\nbinarySearch");
_grade(binarySearch(S, 0) == 0);
_grade(binarySearch(S, 6) == 4);
_grade(binarySearch(S, 9) == 7);
_grade(binarySearch(S, 5) == -1);
_grade(binarySearch(S, -10) == -1);
_grade(binarySearch(O, 0) == 0);
_grade(binarySearch(O, 5) == -1);
_grade(binarySearch(E, 5) == -1);
System.out.print("\nbubbleSort");
{
int[] U_clone = U.clone();
bubbleSort(U_clone);
_grade(areEqual(S, U_clone) == true);
}
System.out.print("\ntreeSort");
{
int[] U_clone = U.clone();
treeSort(U_clone);
// System.out.println(Arrays.toString(U_clone)); // Uncomment to print result
_grade(areEqual(S, U_clone) == true);
}
System.out.print("\nheapSort");
{
int[] U_clone = U.clone();
heapSort(U_clone);
_grade(areEqual(S, U_clone) == true);
}
}
////////////////////////////////////////////////////////////////////////////////
// YOUR CODE STARTS HERE ///////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
public static void main(String[] arguments) {
// int[] array = { 9, 4, 0, 1, 7, 6, 8, 3 };
// System.out.println(Arrays.toString(array));
runAutograder();
}
// Get whether the arrays A and B have all the exact same elements
// in the exact same order.
//
// Worst-case Time: O(?)
// Worst-case Space: O(?)
static boolean areEqual(int[] A, int[] B) {
// TODO
return false;
}
// Get whether the array is sorted.
// The empty array is considered to be sorted.
// NOTE: For us, sorted means "in ascending order."
//
// Worst-case Time: O(?)
// Worst-case Space: O(?)
static boolean isSorted(int[] array) {
// TODO
return false;
}
// Get the index of the first element in array with this value.
// Returns -1 if no such element exists.
//
// Worst-case Time: O(?)
// Worst-case Space: O(?)
static int linearSearch(int[] array, int value) {
// TODO
return -1;
}
// Get the index of an element in array with this value.
// Returns -1 if no such element exists.
// NOTE!: array must be sorted; otherwise returns nonsense.
//
// Worst-case Time: O(?)
// Worst-case Space: O(?)
static int binarySearch(int[] array, int value) {
// TODO
return -1;
}
// Sorts the array in-place using bubble sort.
// NOTE: Best-case runtime is better than worst-case runtime.
//
// Worst-case Time: O(?)
// Best-case Time: O(?)
// Worst-case Space: O(?)
static void bubbleSort(int[] array) {
// TODO
// HINT: Look up bubble sort on Wikipedia.
}
// Sort the array using (out-of-place) tree sort.
//
// 1) Build a BinarySearchTree object out of the array.
//
// No work-arounds allowed.
// You MUST implement an add function, and use it like this:
//
// for (int element : array) {
// binarySearchTree.add(element);
// printBinaryTree(binarySearchTree.root);
// }
//
// 2) Traverse the binary search tree
// (using the appropriate traversal order)
// to gather the elements in sorted order.
//
// NOTE: You can (and should) write more functions.
// NOTE: You must document all functions you write.
//
// Worst-case Time: O(?)
// Worst-case Space: O(?)
static void treeSort(int[] array) {
// TODO
}
static class Node {
int value;
Node rightChild;
Node leftChild;
}
static class BinarySearchTree {
Node root;
void add(int value) {
// TODO
}
}
// Sort the array using implicit heap sort (swaps only).
//
// 1) "Heapify" the array.
//
// (Turn the array into an implicit max binary heap using swaps.)
//
// [ unsorted-array]
// [ implicit-head | unsorted-array ]
// [ implicit-heap ]
//
//
// 2) Repeatedly swap the last node/element of the heap with
// the 0-th element/max element/root of the heap,
// then sink it down into the remaining heap.
//
// The max element is "removed" into the right side of the array,
// where the sorted array is built up incrementally.
//
// [ implicit-heap | sorted-array ]
//
// Worst-case Time: O(?)
// Worst-case Space: O(?)
static void heapSort(int[] array) {
// TODO
}
////////////////////////////////////////////////////////////////////////////////
// YOUR CODE ENDS HERE /////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
static void _grade(boolean shouldBeTrue) {
System.out.print(shouldBeTrue ? '+' : '-');
}
////////////////////////////////////////////////////////////////////////////////
// GROSS NOT GOOD CODE TO PRINT A BINARY TREE //////////////////////////////////
////////////////////////////////////////////////////////////////////////////////
static void printBinaryTree(Node root) {
if (root == null) {
System.out.println("root is null");
return;
}
class MagicNode {
boolean isNull;
int value;
int depth;
Node leftChild;
Node rightChild;
MagicNode(Node node, int depth) {
if (node == null) {
isNull = true;
} else {
this.value = node.value;
this.leftChild = node.leftChild;
this.rightChild = node.rightChild;
}
this.depth = depth;
}
}
int maxDepth = _maxDepthHelper(root, 0);
System.out.println();
int[] numNodesAtDepth = new int[maxDepth + 1];
int depth = -1;
ArrayDeque<MagicNode> queue = new ArrayDeque<>();
queue.add(new MagicNode(root, 0));
while (!queue.isEmpty()) {
MagicNode curr = queue.remove();
boolean first = (curr.depth != depth);
if (first) depth = curr.depth;
int k = maxDepth - depth;
int pre = (1 << (k + 1)) - 2;
int intra = (1 << (k + 2)) - 1;
if (first) {
System.out.println();
if (depth != 0) { // branches
// a b c b a
int a0 = (1 << (k + 2)) - 2; // FORNOW (pre(k + 1))
int a = a0;
int b = -1;
int c = (1 << (k + 3)) - 1; // FORNOW (intra(k + 1))
MagicNode[] _FORNOW = queue.toArray(new MagicNode[0]);
ArrayList<MagicNode> FORNOW = new ArrayList<>();
FORNOW.add(curr);
for (MagicNode _fornow : _FORNOW) FORNOW.add(_fornow);
while (b < a0 - 1) {
--a;
b += 2;
c -= 2;
_printSpaces(a);
int i_FORNOW = 0;
for (int rep = 0; rep < (1 << (depth - 1)); ++rep) {
System.out.print((FORNOW.get(i_FORNOW++)).isNull ? ' ' : '/');
_printSpaces(b);
System.out.print((FORNOW.get(i_FORNOW++)).isNull ? ' ' : '\\');
_printSpaces(c);
}
System.out.println();
};
}
_printSpaces(pre); // pre
}
System.out.print((curr.isNull) ? " " : curr.value);
_printSpaces(intra - (_numDigits(curr.value) - 1)); // intra
if (curr.depth < maxDepth) {
queue.add(new MagicNode(curr.leftChild, curr.depth + 1));
queue.add(new MagicNode(curr.rightChild, curr.depth + 1));
}
}
System.out.println();
}
static int _maxDepthHelper(Node curr, int level) {
int left = (curr.leftChild != null) ? _maxDepthHelper(curr.leftChild, level + 1) : level;
int right = (curr.rightChild != null) ? _maxDepthHelper(curr.rightChild, level + 1) : level;
return Math.max(left, right);
}
static void _printSpaces(int numSpaces) {
String spaces = "";
for (int i = 0; i < numSpaces; ++i) spaces += " "; // FORNOW
System.out.print(spaces);
}
static int _numDigits(int n) {
if (n == 0) return 1;
int result = 0;
if (n < 0) {
++result;
n = -n;
}
do {
++result;
n /= 10;
} while (n != 0);
return result;
}
}