binary_sort.markdown

Binary Sort

Instructions

Complete these steps with roles Person 1 (P1) and Person 2 (P2):

• P1 selects 8 of your numbers at random
• P2 walks through the Building the Tree algorithm for those eight numbers out loud without counting steps
• P1 walks through the Traversing the Tree algorithm out loud without counting steps
• P1 adds four new cards, shuffles
• P2 walks through the Building the Tree algorithm while P1 counts the steps using the guidelines below
• P1 walks through the Traversing the Tree algorithm while P2 counts the steps using the guidelines below

Step Counting

Increment your number of steps for each of these operations:

• Compare two numbers
• Insert a node into the tree
• Checking if a node exists

Algorithm

Building the Tree

1. Start with a blank tree template (provided)
2. Insert the first input as your "root" node to the top of the tree
3. Is there an element left in the input?

• If there is one, take it from the input and call it current.
• If there are no more, you're done!

4. Call the root of your tree target.
5. Compare current to target.

• If current is greater, change your target reference one step down to the RIGHT on the tree
• If current is smaller, change your target reference one step down to the LEFT on the tree

6. Is target now blank?

• If it is blank, insert the current there and go to Step 3
• If it is not blank, return to Step 5

Traversing the Tree

The easiest way to traverse the tree is to approach it recursively. Consider this function pseudocode:

traverse(node):
  if node.left
    traverse(node.left)
  print node
  if node.right
    traverse(node.right)

Output the elements of your tree in order by passing your root node into that function and compiling the printed outputs.

Analysis

Discuss and write answers to these questions in your notebook:

1. What would the worst case input set be for this algorithm? What would be the best?
2. Why does it matter if the tree is "balanced" or "unbalanced"?
3. What could you do to your input data to increase the likelihood of getting a balanced-ish tree?
4. Consider the growth of the tree as the number of inputs increases. Does it make you think this is a "good" or "bad" algorithm for large data sets? Why?