Sorting and Runtimes

445 final review

Towers of Hanoi Runtime

2^(N-1) or O(2^N)

Insertion/Selection sort key instruction

The element selected to be compared and sorted to the others

Insertion sort worst case

O(N²)

Insertion sort average case

O(N²)

Insertion sort worst sorted order NORMALLY

Reverse sorted

Insertion sort worst sorted order LINKED LIST

Sorted

Selectionsort best/worst/average case

O(N²)

Bubblesort worst case runtime

O(N²)

InsertionSort best case runtime

O(N)

ShellSort runtime

O(N^(3/2))

MergeSort runtime

O(nlogn)

QuickSort runtime

O(nlogn)

Quicksort worst case runtime

O(N²)

Sorting algorithm that starts at second element and puts it in the correct place based on the first element. Then it does the third element, then the fourth, then the nth element until sorted

Insertion Sort

Sorting algorithm compares adjacent items two at a time until sorted

Bubble Sort

Sorting algorithm finds the smallest element from the unsorted portion continuously and then swaps it with the first element in the unsorted portion

Selection Sort

Sorting algorithm recursively divides array into subarrays, then sorts the subarrays and combines them together one by one

Merge sort

Sorting algorithm chooses a pivot then sorts the algorithms with items smaller on the left and larger on the right. Then each side is recursively sorted

Quick Sort

Sorting algorithm chooses a gap size and sorts items that are a gap size apart. Reduce gap and do it again. Do insertion sort when gap is 1

ShellSort

Is quicksort stable?

No

is MergeSort stable?

Yes

Is MergeSort or QuickSort better for sorting Objects?

MergeSort

RadixSort runtime

O(KN)

What does the K represent in RadixSort runtime

K = max string length

What does N represent in RadixSort runtime?

N = length of the array

Sorting algorithm that begins with rightmost element and puts them into bins, then adds them back to the array based on their compared order.

RadixSort

What are the requirements to use RadixSort?

Elements must be a Fixed Length

Elements must be digit-accessible

What makes a good hashing function?

Utilizes all parts of the key

Exploit all differences of the key

Utilize the full address space of the hash address

Brute force runtime

O(N) normal case
O(MN) worst case (unlikely)

Rabin-Karp runtime

O(N) (LSV very likely not gaurenteed)

O(MN) worst case (LSV version, very unlikely)

Boyer-Moore runtime

mismatched char heuristic leads to O(N/M) best case SUBLINEAR!! and O(MN) worst case

second heuristic guarantees O(N) worst case

Explain Boyer-Moore first heuristic

First character mis-match, skip to next possible location. (EX: if “f” does not appear in pattern, skip to position after the “f”)

Explain the second heuristic in Boyer-Moore algorithm

If part of the pattern matched, then you encounter a mismatch, check if the part that already matched appears elsewhere (the suffix)

How do you “push” in an Array Stack

Add to the end of logical array

How do you “push” in an LinkedList Stack

Push to the front, and Pop from the front

How many levels are there in MergeSort? How much work is required for each?

O(logN) levels with O(N) work

name the methods in Iterator<T>

hasNext, next, and remove

How do we implement iterators?

Make them a private inner class within your ADT

What is the double hashing formula?

(h1(K) + (num of attempts) * h2(K)) mod (size of table)

Load factor formula (how full the table is)

N/M