Flashcards

Computing Paper 2: Algorithms (2.3.3/2.3.4/2.3.5)

Qashrina Collier Computing A level Inglês 8 flashcards

Flashcards do conjunto (8)

1Bubble sortMakes comparisons & swaps between pairs of elements.
O(n^2) = slow
2Insertion sortStarts at 2nd element and compares it to the left. Performs consecutive swaps.
O(n^2)
3Merge sortEXAMPLE: worst time O (n logn)
7, 4, 2, 6
7,4. 2,6
7, 4, 2, 6
4, 7, 2, 6
2, 4, 6, 7
4Quick sortSelects pivot and divides input around it. Elements larger than pivot placed to right. O(n^2).
9,4,7,8,6,3,1,5,2
5Searching algorithms: Linear searchIterates through whole list of items, start to end to find item.
6Searching algorithms: Binary searchCalculates midpoint of ordered list. If item needed lower than midpoint second half of list can be ignored. If higher then first half can be ignored. This process continues until item found.
7Dijkstra's algorithmVertex, shortest distance from node, previous vertex.
Finds best path for algorithm.
8A* star algorithmFinds path by using a heuristic approach (used to provide 'good enough' solutions to complex problems where finding perfect solution would take too much time).