UML Computing II Exam II

Bubble Sort

Starting from the beginning of a list compare adjacent pairs, if they are out of order swap them, do this for the entire list n-1 times.

Selection Sort

The smallest element is selected from a list and swapped with the leftmost element, and that element becomes a part of the sorted array. This process continues, swapping the smallest element found in the unsorted list to the end of the sorted list, do this n-1 times.

Insertion Sort

Assume first item in the list is a sorted list, take the element in the unsorted list that is adjacent to the sorted list and swap it into the correct position in the sorted list, do this n-1 times.

Improvements:

Shifting- Instead of assigning the value of the element you are trying to insert into the sorted list and then comparing again. Compare it to each value until you find the correct index to insert the value into.

Sentinel- Do 1 round of selection sort before doing insertion sort. Do not comparison to the first element in the sorted list (the sentinel).

Shell Sort

h sort the list with decreasing values of h, until and including h = 1. h sort is just insertion sort but instead of looking at items that are 1 apart look at items that are h apart.

Heap Sort

Heapify the array, remove the max n-1 times. Heapify is call fix down on every node of the tree starting from the back of the tree, ignoring leave nodes.

*leave node is a node without any children, a lonely life.

Pre-order Traversal

SLR (self, left, right, the stack method is an easy way to do these)

Video: Lecture Capture, 2:00 pm class

Date: 4/3/19

Timestamp: 19:43

In-order Traversal

LSR

Post-order Traversal

LRS

Complete Tree

Filled top to bottom, left to right

Full Tree

Every node that has a child has the maximum amount of children, in our case that is 2 children.

BST - Binary Search Tree

If value if greater it gets placed to the right, if smaller goes to the left.

Note: These can look extremely ugly, don't ever rotate these.

AVL Tree

Have to understand how to balance the tree and do proper rotations. These ones look nice.

Video: Lecture Capture, 2:00 pm class

Date: 4/3/19

Timestamp: 24:00

Heap

*When solving for the Heap problem insert the numbers 1 at a time, fix up as you insert the numbers.

Make sure that the parent is bigger than the child and fill top to bottom left to right

Heapify

*When solving for the heapify problem put them all in a tree in the order they were listed in the array and then sort it.

Call fix down on every node in the tree, starting from the back of the array, ignoring leaf nodes.

Fix Down

Compare parent to its children, swap it with the largest of its children.

*This is often done recursively, so then after swapping you compare the node just brought in to its new children and swap until you cannot anymore.

Remove Max

To remove the max take the largest value of the nodes and swap it with the lowest and rightmost leave node. Then pretend that the largest node is gone and call fix down until the node that was swapped to the root is now in the right location.

*Doing this to every element of a list creates a sorted list.

Priority Queue

Yes you need to memorize this

link: https://docs.google.com/document/d/1hxlp7lm6N5QmVY4ZYbc6XnTdN9KXe190i3bBwDWRtvA/edit?usp=sharing