Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithms (Data Structures (Trees, Lists, Hashes / Maps / Dictionaries,…
Algorithms
-
Types
-
Finding
Binary Search O(log n)
- Useful only for sorted array
- Divide and conqueror
Linear O(n)
- Useful for sorted and unsorted array
-
Sorting
Insertion sort O(n²)
- O(n²) - each step compares and swaps O(n)
- in-place sort
- Look at left of the list looking for greater than the current while shift positions
Binary insertion sort
It's possible to use B-search do reduce complexity of comparison turning the algorithm O(n log n), however it will need to insert the sorted the element into the new position shifting the other elements to the right turning the algorithm into O(n²) again.
Merge Sort O(n log n)
- Divide and Conquer (Split array A (n) into two arrays L (n/2) and R (n/2), sort them and merge while sorting A)
- Two sorted arrays as input
- Recursive algorithm
- Also know as Two fingers algorithm
- Data merge step is O(n)
- Disadvantage comparing to insertion sort it requires N spaces in memory, because it needs to copy parts of the array
Selection Sort O(n²) / Also known as min sort
- O(n²) - each step compares and swaps O(n)
- in-place sort
- Look at right of the list looking for the min and swap position
-
Quick Sort O(n log n)
- Divide and Conquer dividing the array and sorting ranges (from / to)
- It uses a chosen number as pivot to iterate and find all items less than the chosen one and change the positions to the greater ones
- Recursive algorithm
-