Please enable JavaScript.
Coggle requires JavaScript to display documents.
Paper 2 content: 2.1.1, 2.1.2, 2.1.3 - Coggle Diagram
Paper 2 content: 2.1.1, 2.1.2, 2.1.3
2.1.1 Computational Thinking
2.1.2 Designing, creating and refining algorithms
Flow Diagrams
Pseudocode
2.1.3 Searching & Sorting Algorithms
Searching Algorithms
Binary Search
Binary Search is a type of algorithm that can be very fast but needs an ordered list, such as a dictionary. This searching technique can be used to find spellings and definitions very fast.
Binary Search is only possible for data that is ordered in a list. It HAS to be ordered in a list.
It starts the search from the middle of the list to assess whether the item is positioned higher or lower than the middle
If the item is positioned lower than the middle then the search is narrowed to the first half of the list.
If it is higher than the middle, the search is narrowed to the second half of the list
Once the data list is halved the search starts from the middle of that half again
This method of search can be much quicker than linear by breaking down the list into halves and assessing the middle item to the surrounding items until the item is found
Linear Search
Linear Search is a searching algorithm that simply sorts through a list either sorted or unsorted and simply looks at each item, one at a time, until it finds what it is looking for e.g. looking through a deck of cards to find a certain card.
This method can either be very slow or very fast depending on where the item is in the list as it can be either at the start or at the end or in the middle or anywhere in the list.
Linear Search is the simplest searching algorithm
Sorting Algorithms
Bubble sort
Bubble sort is the simplest sorting algorithm
It is a way of sorting items in ascending order
From the leftmost item, it compares it to the item to the right item. If it is higher than the one on the right then they are swapped. If no swaps take place then the list is already in order, otherwise, the process starts again until the list is ordered.
Merge sort
Merge sort is the most complex sorting algorithm
It repeatedly breaks down the list into halves until every item is on it's own. From this the algorithm then sorts the items which are then joined back up into a fully ordered list
It is far more efficient than insertion and bubble sort algorithms but it is slower on smaller lists and even if the list is already sorted at the start, the process will take place anyway.
Insertion sort
An Insertion Sort algorithm takes each item and puts it in the right place, using the first item as a starting point. For each item it takes, it compares it to all the other items in the list to find the correct place for said item relative to the other items.