COMP.1020 Exam II

Bubble Sort

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.

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. Call fix down on every node in the tree, starting from the back of the array, ignoring leaf nodes.

Quick Sort

Pick a pivot and move it over to the edge of the list. Do an operation so all items that are smaller end up on the left of the pivot and all items that are greater than the pivot end up to the right of it. This is done by first scanning from the right of the list until an item that should be to the left of the pivot is found. Then scan from the left until an item that should be to the right of the pivot is found. Swap them. Do this until the until the scanners both meet at one item. Then swap the pivot in to that location.

Pre-order Traversal

SLR

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.

Heap

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

Heapify

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.

Improvements to Insertion Sort

Sentinel Value and Shifting

What is the shifting improvement for insertion sort?

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.

What is the sentinel improvement for insertion sort?

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