Common Algorithms Flashcards
What are the two most common algorithms?
Search
Sort
What are two common ways of searching?
linear search
binary search
What are two common ways of sorting?
bubble sort
merge sort
How does a linear search happne?
Identify a search term.
Look at the first item in the list.
Compare the item with the search term.
Is the current item the same as the search term? If so, the item has been found. If not, move to the next item.
Repeat from step two until the last item in the list has been reached.
If the end of the list has been reached and the search term has not been found, then the search term is not in the list and the algorithm can stop.
What is a problem with linear searching?
As the list gets longer the algorithm takes longer to run, making it inefficient for large lists.
What does a binary search require?
All items to be sorted first
What is the index?
The position of a piece of data in a list.
What is an integer?
A whole number - this is one data type used to define numbers in a computer program. Integers can be unsigned (represent positive numbers) or signed (represent negative or positive numbers)
How does a Binary search happen?
Start by setting the counter to the middle position in the list.
If the value held there is a match, the search ends.
If the value at the midpoint is less than the value to be found, the list is divided in half, the lower half of the list is ignored and the search keeps to the upper half of the list.
Otherwise, if the value at the midpoint is greater than the value to be found, the upper half of the list is ignored and the search keeps to the lower half of the list.
The search moves to the midpoint of the remaining items. Steps 2 through 4 continue until a match is made or there are no more items to be found.
When is a linear list method better than binary?
Linear search is best used when the data is not in order, or for smaller lists
When is a binary list method better than linear?
When the list is much longer and the data is in order, it is far more efficient to calculate the
indexes needed to perform a binary search.
What is a merge sort?
The merge sort algorithm repeatedly divides a list into two until all the elements are separated individually.
Pairs of elements are then compared, placed into order and combined.
The process is then repeated until the list is recompiled as a whole.
What is a bubble sort?
Each run through the list, from start to finish, is known as a pass. The bubble sort continues until a pass is made where no values have been swapped. At this point, the list is sorted.
The algorithm runs as follows:
Look at the first number in the list.
Compare the current number with the next number.
Is the next number smaller than the current number? If so, swap the two numbers around. If not, do not swap.
Move to the next number along in the list and make this the current number.
Repeat from step 2 until the last number in the list has been reached.
If any numbers were swapped, repeat again from step 1.
If the end of the list is reached without any swaps being made, then the list is ordered and the algorithm can stop.
