DSA
Big O analysis applied back to the sorting algorithms already covered, so runtime tradeoffs become concrete.
To fully understand algorithms we must understand how to evaluate the time an algorithm needs to do its job, the runtime.
See the earlier lesson for a general explanation of what time complexity is.
The Selection Sort algorithm goes through all elements in an array, finds the lowest value, and moves it to the front of the array, and does this over and over until the array is sorted.
The worst case scenario for Insertion Sort is if the array is already sorted, but with the highest values first. That is because in such a scenario, every new value must "move through" the whole…
The Quicksort algorithm chooses a value as the 'pivot' element, and moves the other values so that higher values are on the right of the pivot element, and lower values are on the left of the pivot…
Counting Sort works by first counting the occurrence of different values, and then uses that to recreate the array in a sorted order.
The Radix Sort algorithm sorts non negative integers, one digit at a time.
The Merge Sort algorithm breaks the array down into smaller and smaller pieces.
Linear Search compares each value with the value it is looking for. If the value is found, the index is returned, and if it is not found -1 is returned.
Binary Search finds the target value in an already sorted array by checking the center value. If the center value is not the target value, Linear Search selects the left or right sub-array and…