CS data structures

Selection Sort

Selects the largest or smallest element to swap with.

Insertion sort

Inserts the first unsorted element to the front.

Bubble sort

The largest or smallest element bubbles up

Merge sort

Splits the data set in half and merge in order with the auxillary arrays

Quick sort

Makes an element a pivot and sorts it based on it.

Radix sort

Sorts based on the element’s length and content

Heap sort

Maximum or minim numbers get sorted as highest priority

Time complexity for Selection sort

Best case: O(n^2)

Average: O(n^2)

Worst case: O(n^2)

Time complexity for Insertion Sort

Best case: O(n)

Average: O(n^2)

Worst case: O(n^2)

Time complexity for Bubble Sort

Best case: O(n)

Average: O(n^2)

Worst case: O(n^2)

Time complexity for Merge sort

Best case: O(nlogn)

Average: O(nlogn)

Worst case: O(nlogn)

Time complexity for Quick sort

Best case: O(nlogn)

Average: O(nlogn)

Worst case: O(n^2)

Time complexity for Radix sort

Best case: O(n \* k)

Average: O(n \* k)

Worst case: O(n^2)

Time complexity for Heap sort

Best case: O(nlogn)

Average: O(nlogn)

Worst case: O(nlogn)

Linked List

A list of pointers pointing to each other in one way.

Stack

A linked list that goes with “First in, Last out”

Queue

A linked list that goes with “First in, First out”

Set

Unordered collection of elements

Hash table

An array of elements that are inserted based on their hash codes

Binary Search Tree

A data structure that has two children, left ones are smaller and right ones are larger

Maps

Data structure that associates a key with a value

Red-Black Tree

A self-balancing tree that utilizes color codes to balance itself

Node

Building block of a tree

Ancestor

Nodes above the current node

Descendant

Nodes below the current node

Child

A node that is below the current node and is linked left or right

Interior node

Node that is not a leaf

Parent

The previous linked node of the current node

Sibling

The node that is also a child of the current node

Root

Node with no parent

Time complexity for Linked List

Add: O(1), O(n) in middle

Remove: O(1), O(n) in middle

Search: O(n)

Time complexity for Stack

Add: O(1)

Remove: O(1)

Search: O(n)

Time complexity for Queue

Add: O(1)

Remove: O(1)

Search: O(n)

Time complexity for Hash table

Add: O(1)+

Remove: O(1)+

Search: O(1)

Iterate: O(n)

Time complexity for Binary Search Tree

Add: O(logn)/O(n)

Remove: O(logn)/O(n)

Search: O(logn)/O(n)

Time complexity for Heap

Add: O(nlogn)

Remove: O(nlogn)

Search: O(logn)

How much merges would be needed for an array of n length?

N - 1 merges

How many more times would you need to merge if you double the array size of n length?

1 more time

What search to use if you are only searching once?

Linear

What search process to use if you are searching multiple times in an unsorted data set?

Quick sort then binary sort

For insertion sort for sorted lists, if the time to sort 10 items is 4 seconds, the time for 30 items is

12 seconds

What is the Big Oh growth rate of 5000000n + 343242342?

O(n)

Linear search time complexity

O(n)

Binary search time complexity

O(nlogn)

What would be the best data structure to store blocked websites?

Set

Time efficiency to printing out all nodes of a Red-Black tree

O(n)

Time efficiency to printing out all nodes of a Red-Black tree

O(

Adding/removing from a stack/queue array time efficiency

O(1)+

Unordered sets/maps are more efficient than ordered ones

True

What does a good hash function do?

Reduce collisions and makes finding easy

Inorder traversal

Left, center, right

Pre-order traversal

Center, left, right

Post-order traversal

left, right, center