| Name of Algorithm | Time Complexity | Space Complexity | Comment | Implementation |
|---|---|---|---|---|
| linear search | O(n) | O(1) | Rarely used. Used for sorted arrays. |
linear.py |
| binary search | O(log(n) | O(1) | Used for sorted arrays. | binary.py |
| jump search | O(n^0.5) | O(1) | Combines binary search and linear search. Used for sorted arrays. Optimal jump size is n^0.5 Time complexity is between linear search and binary search. |
jump.py |
| interpolation search | average case: O(log2(log2 n)) worst case: O(n) |
O(1) | Used for sorted arrays with uniform distribution. Similar to binary search, different method of calculating position. |
interpolation.py |
| exponential search | O(log(n) | O(1) | Used for sorted arrays. Divides array by exponential factor. Than uses binary search on specific slice of the original array. |
exponential.py |
| ternary search | O(log3 n) | O(1) | Used for sorted arrays. Similar to binary search, the difference is that we divide array (or slice) into 3 parts instead of 2 parts. |
ternary.py |
| selection sort | O(n) | O(1) | selection.py | |
| bubble sort | worst / average case: O(n^2) best case: O(n) |
O(1) | bubble.py | |
| insertion sort | O(n*2) | O(n) | insertion.py | |
| merge sort | O(n*log(n)) | O(n) | merge.py | |
| quick sort | worst case: O(n^2) average case: O(n*log(n) best case: O(n) |
O(log(n)) | quick.py | |
| heap sort | On*log(n)) | O(1) | heap.py | |
| count sort | O(n + k): 0>k>=n | O(n+k) | Best for small range of values (k). | count.py |
| radix sort | O(d*(n+b)) d- number of digits n- number of elements b- system base |
O(b+n) | radix.py | |
| bucket sort | average case: O(n+k) worst case: O(n^2) |
O(n+k) | Best for uniformly distributed values. Breaks list into sublists and uses another algorithm to sot them. |
bucket.py |
| shell sort | O(n^2) | O(1) | shell.py | |
| comb sort | O(n^2/2^p) p- number of increments n- number of elements |
O(1) | comb.py | |
| pigeonhole sort | O(R+n) R- range of values n- number of elements |
O(n) | pigeonhole.py | |
| cycle sort | O(n^2) | O(1) | cycle.py |
