Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms and Data Structures - Coggle Diagram
Algorithms and Data Structures
Algorithms
Sorting
Heap Sort
Best: O(n log(n))
Average: O(n log(n))
Worst: O(n log(n))
Space worst: O(1)
Quick Sort
Best: O(n log(n))
Average: O(n log(n))
Worst: O(n2)
Space worst: O(1)
Bubble Sort
Best O(n)
Average: O(n2)
Worst: O(n2)
Space worst: O(1)
Selection Sort
Best: O(n2)
Avarage: O(n2)
Worst: O(n2)
Space worst: O(1)
Merge Sort
Best: O(n log(n))
Average: O(n log(n))
Worst: O(n2)
Space worst: O(n)
Insertion Sort
Best: O(n)
Average: O(n2)
Worst: O(n2)
Space worst: O(1)
Shell Sort
Bucket Sort
Radix Sort
Search
Hash table
Binary
O(log(n))
Looks at array and decides which side to look for the search trerm
starts with sorted array
Linear
Goes through each element
Slowest when search term is last O(n)
Fastest when the search term is first O(1)
Style
Divide and conquer
Recursive
3 laws
call itself, recursively
must have a base case
must change state to base case
Brute force
Iterative
Data Structures
Primitives
Blob
binary primitive
typically used in databases
Double
Float
Integer
String
Character
Objects
(Non-Primitive)
Linear Data Structures
Array
Stack
Queue
Priority Queue:
Can be assigned to anable a particular process without affecting ovarall system operation.
FIFO rule is broken in these situations.
In preority queues, elements are dequeued according to their priority and their current queue position
Operations:
Java
add(T el): Insert element el in this priority.
NullPointerException if el is null
ClassCastException if the order used by this priority queue cannot be applied to el.
clear(): Remove all the elements from this priority queue.
Comparator<? super T> comparator()
: Return a comparator to be used to order elements of this priority queue or null if elements are ordered with the method compareTo().
contains(Object el): Return true if element el is in this priority queue.
offer(T el): Insert element el in this priority.
NullPointerException if el is null.
ClassCastException if the order used by this priority queue cannot be applied to el.
Linked List
Non Linear Data Structures
Tree
Tree is an abstract model of a hierarchical structure
A tree consists of nodes with a parent-child relation
Applications: Organization charts, File systems, Programming environments
Internal node
: Node with at least one child
External(leaf) node
: Node without children
Sub tree
: A node with its descendants
Level(depth) max = height
Binary Tree
Binary Heap
Priority Queue
Binary Search Tree
AVL Tree
Ordered Tree
Tree traversal
Process of visiting each node
in the tree exactly one time
Post-order travelsal
A node is visited after its descendants
Breadth-first traversal
A node is visited first, then all it's children, then all its grandchildren,....
Pre-order traversal
A node is visited before its descendants
terms
Edge
Height
Parent, Child, Silbing
Node - key (name) that can have payload
Root
Path
Graphs
Travel
Breadth First
Depth First
DIijkstra's Algorithm
Complexity: O(|V|2)
Floy's Algorithm
Complexity: O(|V|3)
terms
Edge (directed or undirected) - Arc
Weight
Node - Vertex with key (name) that can have payload (value)