Paper 2 Search Algorithms Flashcards
Describe how a binary search works.
A binary search is an efficient method of searching an ordered list.
A binary search works like this:
1) Start by setting the counter to the middle position in the list.
2) If the value held there is a match, the search ends.
3) 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.
4) 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.
5) 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
Describe how a linear search works.
A linear search is the simplest method of searching a data set.
Starting at the beginning of the data set, each item of data is examined until a match is made. Once the item is found, the search ends. If there is no match, the algorithm must deal with this.
What is the purpose of the ‘Bubble Sort Algorithm’?
Bubble sort is a basic algorithm for arranging a string of numbers or other elements in the correct order. The method works by examining each set of adjacent elements in the string, from left to right, switching their positions if they are out of order. The algorithm then repeats this process until it can run through the entire string and find no two elements that need to be swapped.
Describe how the ‘Bubble Sort’ works.
The ‘Bubble Sort’ runs as follows:
1) Look at the first number in the list.
2) Compare the current number with the next number.
3) Is the next number smaller than the current number? If so, swap the two numbers around. If not, do not swap.
4) Move to the next number along in the list and make this the current number.
5) Repeat from step 2 until the last number in the list has been reached.
6) If any numbers were swapped, repeat again from step 1.
7) If the end of the list is reached without any swaps being made, then the list is ordered and the algorithm can stop.
Describe how the ‘Merge Sort’ works.
A merge sort uses a technique called divide and conquer. The list is repeatedly divided 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.
Describe how the ‘Insertion Sort’ works.
An insertion sort compares values in turn, starting with the second value in the list. If this value is greater than the value to the left of it, no changes are made. Otherwise this value is repeatedly moved left until it meets a value that is less than it. The sort process then starts again with the next value.
