Algorithm Efficiency Aqa

课 Progress

0% Complete

Exam code:8525

Algorithm Efficiency

Algorithm efficiency is how much time it takes to complete an algorithm
In programming, there is often more than one algorithm which can solve a problem
An example of this is a linear search and binary search as both find a value in a list, however, depending on the circumstances, one may be much faster than the other

If we took the numbers 1-20 jumbled up in a list
How efficient an algorithm is would be determined by how quickly it could sort the numbers into ascending order

Sort 1 (Bubble sort)	Sort 2 (Insertion sort)
`DEFINE listToSort AS a list of integers containing the numbers 1 to 20` `SET lengthOfList TO the length of listToSort` `FOR currentIndex FROM 0 TO lengthOfList - 1 DO` `FOR innerIndex FROM 0 TO lengthOfList - 1 - currentIndex DO` `IF listToSort[innerIndex] > listToSort[innerIndex + 1] THEN` `TEMP ← listToSort[innerIndex]` `listToSort[innerIndex] ← listToSort[innerIndex + 1]` `listToSort[innerIndex + 1] ← TEMP` `END IF` `END FOR` `END FOR`	`DEFINE listToSort AS a list of integers containing the numbers 1 to 20` `SET lengthOfList TO the length of listToSort` `FOR currentIndex FROM 1 TO lengthOfList - 1 DO` `SET currentValue TO listToSort[currentIndex]` `SET innerIndex TO currentIndex - 1` `WHILE innerIndex >= 0 AND listToSort[innerIndex] > currentValue DO` `listToSort[innerIndex + 1] ← listToSort[innerIndex]` `SET innerIndex TO innerIndex - 1` `END WHILE` `listToSort[innerIndex + 1] ← currentValue` `END FOR`

Sort 1 (Bubble sort)

Sort 2 (Insertion sort)

DEFINE listToSort AS a list of integers containing the numbers 1 to 20

SET lengthOfList TO the length of listToSort

FOR currentIndex FROM 0 TO lengthOfList - 1 DO

FOR innerIndex FROM 0 TO lengthOfList - 1 - currentIndex DO

IF listToSort[innerIndex] > listToSort[innerIndex + 1] THEN

TEMP ← listToSort[innerIndex]

listToSort[innerIndex] ← listToSort[innerIndex + 1]

listToSort[innerIndex + 1] ← TEMP

END IF

END FOR

DEFINE listToSort AS a list of integers containing the numbers 1 to 20

SET lengthOfList TO the length of listToSort

FOR currentIndex FROM 1 TO lengthOfList - 1 DO

SET currentValue TO listToSort[currentIndex]

SET innerIndex TO currentIndex - 1

WHILE innerIndex >= 0 AND listToSort[innerIndex] > currentValue DO

listToSort[innerIndex + 1] ← listToSort[innerIndex]

SET innerIndex TO innerIndex - 1

END WHILE

listToSort[innerIndex + 1] ← currentValue

END FOR

In the algorithms above, the worst case of a bubble sort is that it would take 361 comparisons to sort 20 items of data
The worst case of an insertion sort with 20 items is that it would perform 190 comparisons
This means that in this instance, although both algorithms perform the same job and achieve the same result, an insertion sort would be significantly faster because it is much more efficient in how it uses the computer’s processing power and memory