- Computational Complexity
- Bubble Sort
- Insertion Sort
- Merge Sort
- Quick Sort
- worst-case scenario:
- best-case scenario:
- theta, , if the running time of an algorithm is the same in the worst-case () and the best-case ().
- We don't actually care about how complex the algorithm is precisely, only it's tendency, which dictated by the highest-order term.
- for example, , , . when
nis 1,000,000, the values will be , and . The lower terms became really irrelevant. So we only take the highest-order term, which is here.
- for example, , , . when
- from fast to slow:
- constant time
- logarithmic time
- binary search
- linear time
- linear search
- linearithmic time
- merge sort
- quadratic time
- bubble sort, selection sort, insert sort
- polynomial time
- exponential time
- factorial time
- infinite time
- More comparisons: https://en.wikipedia.org/wiki/Sorting_algorithm#Comparison_of_algorithms
for each element in array if element you're looking for return true return false
look at middle of array if element you're looking for return true else if element is to left search left half of array else if element is to right search right half of array else return false
- find the smallest element, and move it to the front of the list and shift the other ones down, until hit the end.
for i from 0 to n-1 find smallest element between i'th and n-1'th swap smallest with i'th element
- from left to right and compare each pair of numbers. If they are out of order, then swap them.
repeat until no swaps for i from 0 to n-2 if i'th and i+1'th elements out of order swap them
- Each time, we look at the next element and place it into our sorted portion of the list, even if we have to shift elements.
for i from 1 to n-1 call 0'th through i-1'th elements the "sorted side" remove i'th element insert it into the sorted side in order
- First divide the list into the smallest unit (1 element), then compare each element with the adjacent list to sort and merge the two adjacent lists. Finally all the elements are sorted and merged.
on input of n elements if n < 2 return else sort left half of elements sort right half of elements merge sorted halves
Calculate the complexity: :
cis the single step takes. In this case, c = 1, cause we only need to put an element into memory.
- Then use formula:
T(n) = T(n/2) + T(n/2) + n.
nmeans every layer will take
nsteps. When the array has been separated as one by one, we will need
1 * nsteps to sort them all, then
2 * n/2steps, then
4 * n/4step. So every steps will take
nsteps to sort.
- So the complexity will be : .
- Implement with Python 3
pick an element called a pivot from array partition the array with pivot if element i > pivot move to right in the end swap the pivot to middle() recursively apply steps before to the left and the right sub-array without pivot