2.3 Algorithms

Knowledge and Understanding • All adjacent items are compared against each other. • The biggest number in the adjacent pair is swapped over with the smallest number. A temp variable is used to hold the data while it’s being moved. • When a swap is made a flag is set. • This is repeated for all adjacent values, known as one pass. • At the end of one pass, the largest item should appear at the end of the list. • If at the end of the list the flag has been set the flag is unset and the algorithm starts from the beginning of the list again. • When the algorithm gets to the end of the list and the flag is unset the list is sorted. Application • As there are 250,000 items a bubble sort would perform very slowly as a lot of passes will need to be made in order to sort the items. • Bubble sorts are better suited to data sets where the items are almost/partly sorted. However the smaller numbers are currently towards the end and the larger numbers are towards the start. • This will therefore increase the amount of comparisons / passes/swaps required which will therefore slow the performance of the sort down. Evaluation • The algorithm is easy to implement as the number of lines of code is less than other standard sorting algorithms. • Although a bubble sort will be able to sort the items into order, it will take longer than other sorting algorithms due to the number of items and the current order or items in the unsorted list.

AO1: Knowledge and Understanding Indicative content O(1) • Constant space, does not change O(n) • Linear • Same as number of elements • As number of elements increases so does the time/space O(n2) • polynominal • As number of elements increases, time/space increases by *n O(n log(n)) • Linearithmic AO2: Application • Space: Merge sort will require more memory usage as the number of elements increases. Insertion will not require any more space than original. Quick will increase but not as much as merge. • Best time: Insertion increases at the same rate as the number of elements. Quick and merge increase at greater rate • Worst time: insertion and quick increase significantly by n for each additional item. Merge sort increases less per element. • Log more appropriate for large number of elements AO3: Evaluation e.g. • Small array – space is not important. Few number of elements. Look for consistency Large array therefore memory important – could remove merge as inappropriate. Logarithmic more efficient.