2.1.3 Searching and sorting algorithms

Linear search

• lEach data item is searched in order from the first value to the last - sequential

• List does not have to be in any order before it is searched

• Not very efficent for large lists

key features

• a loop is used to check the first value in a list and increment by 1, checking each value for a match to the target

• reaching the last element of the list without finding a match means the value is not included

Binary search

• much more efficient as it generally searches through fewer data and is often must quicker - especially for large data sets

• the middle point of the data is selected with each iteration and compared to the value being searched for

• when the midpoint matches the target value, it has been found and the search can stop

• a prequisite (condition that must be satisfied before an algorithm will work correctly) of binary search is that the data must already be sorted

key features

• a midpoint, lowpoint and highpoint are calculated

• a while loop is used to repeatedly compare the midpoint to a target value

• the upper half or lower half of the data is ignored if the midpoint does not equal the target

Merge sort

• divides a list into half repeatedly until each data item is seperate

• then the items are combined in the same way as they were divided but now in the correct order

• when the individual lists are all merged together as one list again, the data is in order and the algorithm will end

key features

• algorithm calls itself from within the subroutine (recursive algorithm

• continually splits sublists into a left side and a right side until each sublist has a length of 1

Bubble sort

• comparison of adjacent data elements

• swapped if they are not in the right order

• algorithm will only stop when a complete iteration through the data is completed with no swaps made

• at the end of one interation through the list, the largest item is at

  the end of the list

• not suitable for large sets of data

key features

• uses an outer while loop to check no swaps have been made

• inner for loop to repeat through the ength of the data set

• uses a flag (a boolean value) to track if a swap has been made and uses a temporary value to help correctly swap

Insertion sort

• list is logically split into sorted vales (on the left) and unsorted values (on the right)

• starting from the left, values from the unsorted part are checked and inserted at the correct position in the sorted part

• this continues through all elements of the list until the last item is reached, and sorted

• efficient for small data sets but would be slow to sort large lists compared to alternatives

key features

• uses an outer for loop to iterate through each value in the list

• uses an inner while loop to find the current value’s correct position in the sorted part of the list

• moves backwards to find the correct position of each value by decreasing the index within