2.3 Flashcards
Linear Search
Not sorted list. Goes through list one by one until value is found or the end has been reached with no found value.
Binary Search
Sorted list. Middle of the list is found and the value is compared with the value being searched for, Then cuts off half the list and finds a new value, keeps going until the value is found or not in the list.
Bubble Sort
The algorithm starts at the first element in an array and compares it to the second. If they are in the wrong order, the algorithm swaps the pair. Otherwise, the algorithm moves on. The process is then repeated for every adjacent pair of elements in the array until the end of the array is reached. The process fully repeats until no swaps are made in a pass.
Insertion Sort
It takes the first number and sets it as a sorted list with the other numbers being a part of a unsorted list. It then takes the first number from the unsorted list and compares it with the numbers in the sorted list. This repeats until there are no more numbers in the unsorted list.
Merge Sort
Splits down into individual pairs and then splits the pairs and compares them. Once compared the pairs go back together but in the right order. This then happens again and again until all the numbers are back in the same list and sorted.
Quick Sort
Quick sort works by selecting an element, often the central element (called a pivot), and dividing the input around it. Elements smaller than the pivot are placed in a list to the left of the pivot and others are placed in a list to the right. This process is then repeated recursively on each new list until all elements in the input are old pivots themselves or form a list of length 1.
What are Heuristics?
Used to find an approximate solution to a problem when the standard solution is unreasonably time-consuming or resource-intensive to find. The solution found through using heuristics is not perfectly accurate or complete; however, the focus is on finding a quick solution that is ‘good enough’.
