Flashcard 20231215
Date: 20231215
Sorting
Explain how the bubble sort algorithm works
The bubble sort algorithm is an algorithm that arranges a list in sorted order.
The bubble sort algorithm goes through a list, starting from the first and compares pairs of numbers, and swaps them if the first number in the pair is larger than the second number in the pair.
The pair is not swapped if the second number is higher than the first number.
This process is performed on each pair of consecutive numbers. Then repeated until there is a situation when after comparing each pair of numbers there is no change.
Explain how the selection sort algorithm works
Explain how the insertion sort algorithm works
Explain how the merge sort algorithm works
Explain how the quick sort algorithm works
Explain how the heap sort algorithm works
Searching
Explain how the linear search algorithm works
The linear search algorithm is a search algorithm.
This is approach is interchangeable with a brute force approach.
Each item in a list is examined until the desired item is found.
Explain how the binary search algorithm works
The binary search algorithm is a search algorithm.
This algorithm depends on the list/array that is being searched through to be in sorted order.
The binary search algorithm works by reducing the search area by 2 until the desired item is found.
With a sorted list / array as input the item in the middle of the array is compared to the desired value, if the desired value is less than the item in the middle of the array then we continue to look for the item in the first half of the array and discard the second half of the array.
This process of comparing the desired item to the item in the midpoint of subsequent arrays is continued until the desired item is found, or until you are left with a single item array which does not match the desired outcome, in which case the desired item is not in the list/array.
Explain how the jump search algorithm works
The jump search algorithm is a search algorithm
The jump search aims to improve on the linear search algorithm by reducing the number of comparisons or tests that need to be performed.
The jump search algorithm relies on a sorted list/array.
The jump search algorithm works by jumping a fixed amount (normally the square root of the length of the list) and comparing the item in the list at that position with that desired item. If the item at that position is more than the desired item then each item between this item and the position of the previously checked item is checked.