Please enable JavaScript.
Coggle requires JavaScript to display documents.
Search & Sort Algorithms and Data Structures (Sort (Quick Sort…
Search & Sort Algorithms and Data Structures
Search
Binary Search
Starts with a sorted array
Looks at the array and decides which side to look for the search term
O(log(n))
Linear Search
Fastest when the search term is first O(1)
Slowest when the search term is last O(n)
Goes through each element
Binary Search Tree
Uses a binary tree graph
follows the graph to find the search term
Requires that the data be in a tree data structure
Data Types/Structures
Primitives
Integer
any non-fractional number
String
Has a length of more than 1
Made up of characters
Float
a decimal approximation combined with an integer
Double
a decimal approximation combined with a wider set of integers
Blob
a binary primitive
typically used in databases
Character
Has a length of 1
Usually a symbol defined in ASCII or UTF-8
Objects
Array
Variations
Queue
FIFO - First in First Out
Typically used when the order of transactions is critical
Stack
LIFO - Last in First Out
Typically used in a recursive fashion where "Backtracking" is required
uses integers as the index
typically cannot expand
Hash Map (Dictionary) (Map)
This is strictly a "key-value" mapped storage structure
Used in Some types of databases as an "index" for quick 1-1 key-value access
Associative Array
Can use integers or have mapped "keys", languages like PHP and JavaScript support this type of structure and is the actual type.
Typically you can push to this data structure as it can expand indefinitely
Graphs
Node Map of any type or structure
Variations
Linked List
This a node based linear structure with a head (aka root)
can only have one child under a node
Binary Tree
This a node based tree structure
can have 2 children under a node
typically used in databases as an "index" for quick less-than or greater than operations
has a root
General Tree
Has a root
can have any number of children under a node
does not need a root but most variations do
typically used for maps and polygon mapping
Sort
Bubble Sort
Slowest: Reverse Sorted Array O(n^2)
Fastest: Sorted Array O(n)
The simplest version of this algorithm always has a speed of O(n)
Insertion Sort
Fastest Reverse Sorted Array O(n)
Slowest: Sorted Array O(n^2)
Merge Sort
start off with a random array of things, keep splitting them until you have 1 item in each array, merge them in order
O(n log(n))
Predictable since the size of the array is most important and will determine the speed of the sort
For database engines, this is used quite often due to its stable properties (stable means that the order of same rank elements will stay the same)
Quick Sort
Fastest: When pivots stay in the center for a randomly ordered array. O(n)
Slowest: When pivot is moving a lot in a sorted or reverse sorted array O(n^2)
This algorithm is used when it is almost assured that the data will be randomly ordered.
This is an unstable partitioning sort. (Unstable means the order will change for elements in the same order rank)
O(n) Speed and Structure Relationship
How are these related?
When should you think about the data structure?
How can you identify the data structure to use?