6414358
Description
Mind Map by Karl Taylor, updated more than 1 year ago
|
|
Created by Karl Taylor
over 7 years ago
|
|
Chapter 5
- Sorting Algorithms
- Bubble Sort
- Repeatedly steps through the list to
be sorted, compares each pair of
items beside each other and swaps
them if they are in the wrong order.
- Repeatedly steps through the list to
be sorted, compares each pair of
items beside each other and swaps
them if they are in the wrong order.
- Insertion Sort
- Works by dividing the list into
two parts: sorted and unsorted
- Elements are inserted one by
one into their correct
position in the sorted section
- Works by dividing the list into
two parts: sorted and unsorted
- Merge Sort
- Quicksort
- Steps
- 1. Take the first item in the list, make it
a list one item big and call it the pivot
- 2. Splits the remainder of the list into two sub-lists: those less
than or equal to the pivot and those greater than the pivot
- 3. Recursively apply step 2 until all sub-lists are pivots
- 4. The pivots can now be combined to form a sorted list
- 1. Take the first item in the list, make it
a list one item big and call it the pivot
- Steps
- Bubble Sort
- Search Algorithms
- Linear Search
- Methodically searches one location after
another until the searched-for value is found
- Methodically searches one location after
another until the searched-for value is found
- Binary Search
- Works by dividing the list in two each time
until we find the item being searched for
- The list must be in order
- Works by dividing the list in two each time
until we find the item being searched for
- Linear Search
- Complexity
- O(x)
- X = worst case complexity
of the algorithm
- X = worst case complexity
of the algorithm
- n = number of data
- Constant complexity
- O(1)
- Takes the same amount of time to run
regardless of the size of a data set
- Takes the same amount of time to run
regardless of the size of a data set
- O(1)
- Linear complexity
- O(n)
- Increase at the same rate
as the input size increases
- Increase at the same rate
as the input size increases
- O(n)
- Polynomial complexity
- O(n to the power of
k) (where k>=0)
- O(n to the power of
k) (where k>=0)
- Exponential complexity
- O(k to the power
on n) (where k>0)
- O(k to the power
on n) (where k>0)
- Logarithmic complexity
- O(Log n)
- O(Log n)
- O(x)
- Shortest path algorithms
- Dijkstra's algorithm
- Finds the shortest path
between two points
- Finds the shortest path
between two points
- A* search
- Uses heuristic to find
the shortest path
between two points
- Uses heuristic to find
the shortest path
between two points
- Dijkstra's algorithm
Want to create your own Mind Maps for free with GoConqr? Learn more.