1.12 Sorting and Searching

starts at the beginning and completes the same task over and over again until a solution is found

repeatedly breaks down the problem into smaller sub-problems, until they are easy to solve. then solving these and combining the solutions

a brute force algorithm - looks at every possible item to see if it is the solution: starts at the beginning of the array and goes through it, item by item, until it finds the data it is looking for or reaches the end of the array without finding it. (can be made more efficient by sorting the list, as it can stop searching once it has gone past where the target should be, although atp just use binary search)

list must already be sorted uses a divide and conquer method the median item is repeatedly selected to reduce the size of the list to be searched. if the selected number is too high, the group of items below will be searched, and vice versa

best: item is first in the array worst: item is last in the array

best: item is in first median position worst: the maximum number of medians are calculated

if the list is to be searched just once, use linear search if there is a large list that will be searched many times, then you should sort it and use binary search

starts at one end of the list and compares data items. if they are in the wrong order, they are swapped. the comparison of pairs continues to the end of the list, each complete traversal of the list is called a pass the process is repeated until there are no swaps during a pass, indicating that the items must be in the correct order

• stopping once no swaps were made during a single pass • reducing the number of comparisons by 1 after each pass

bubble sort is this does not need to make copies of the array - in this way uses memory efficiently

using recursion to divide a list into 2 smaller lists and then those into 2 smaller lists … until size of each list is 1 then solving all of the 1 lists, putting them in to 2-length lists solving these and combining them into 4-length lists… you combine lists by comparing the first of each list repeatedly

use bubble sort for small amounts of data and one-off tasks, with few execution time constraints - simple to understand and simple to code use merge sort for large amounts of data that must be sorted quickly - uses more memory and is more complex to code than bubble sort