2.3.
Algorithms
The use of algorithms to solve problems, and standard
algorithms.
Specification
Our approach this term
You will already be familiar with some of this topic including aspects
of (e) and (f) related to earlier data structure work.
We will cover (a) – (d) in depth using algorithms from (e) and (f) as
examples, including introducing algorithms that will be new to you.
Analysis and Design of Algorithms
for a given situation
Analysing an algorithm essentially means predicting the resources that
the algorithm requires.
While resources such as memory, bandwidth or hardware can be of
primary importance in some cases, most often it is computational time
that we want to measure.
Computational time (also called "running time") is the number of
primitive operations or steps executed when implementing the
algorithm.
Generally by analysing several candidate algorithms for a problem, we
seek to identify the most efficient one or ones.
We may note too that some candidates perform better in different input
circumstances, and we generally try to examine best case, worst case
and average running times.
Computational Speed
To analyse computational speed accurately we need a model of the
implementation platform that we will use.
A implementation or computer platform is a system that consists
of a hardware device and an operating system that an application,
program or process runs upon. The hardware portion of a computer
platform consists of a processor, memory, and storage. The operating
system acts as an interface between the computer and the user and
also between the computer and the application.
As there are so many different platforms some generic simplification is
required.
In most algorithmic analysis the assumption will be that the generic
platform is a single processor with no concurrent operations and that
each instruction takes a constant amount of time.
Analysis of Insertion Sort Algorithm
45, 19, 16, 49, 36, 75, 23, 8, 78, 67, 16… The Insertion Sort works
45, 19, 16, 49, 36, 75, 23, 8, 78, 67, 16… by examining each item in
19, 45, 16, 49, 36, 75, 23, 8, 78, 67, 16…
the array in turn and
inserting it into the
19, 45, 16, 49, 36, 75, 23, 8, 78, 67, 16…
correct position in the list
19, 16, 45, 49, 36, 75, 23, 8, 78, 67, 16… of items preceding it and
16, 19, 45, 49, 36, 75, 23, 8, 78, 67, 16… itself.
16, 19, 45, 49, 36, 75, 23, 8, 78, 67, 16… It does this by successive
16, 19, 45, 49, 36, 75, 23, 8, 78, 67, 16… comparisons and swaps in
16, 19, 45, 49, 36, 75, 23, 8, 78, 67, 16…
the knowledge that the
preceding list is sorted.
16, 19, 45, 36, 49, 75, 23, 8, 78, 67, 16…
16, 19, 36, 45, 49, 75, 23, 8, 78, 67, 16…
Calculating the running time
Insertion sort on array A Cost times
for j = 1 to len(A)-1 c1 n
key = A[j] c2 n–1
i = j-1 c3 n–1
while i > -1 and A[i] > key c4 Sum of tj from j=2 to n
A[i+1] = A[i] c5 Sum of tj – 1 from j=2 to n
I = I -1
c6 Sum of tj – 1 from j=2 to n
endwhile
c7 n–1
A[i +1] = key
(ignore endwhile & next j statements)
next j
Analysis of Insertion Sort
The running time T(n) is the sum of all the cost * time pairs.
In the best case this is when the array is already sorted and t j is
therefore 1.
It can be shown (the mathematicians among you might try this) that
this gives
T(n) = (c1 + c2 + c3 + c4 + c7)n – (c2 + c3 + c4 + c7)
This is a function in the form an + b for constants a & b, i.e. a linear
function.
In reverse order (worst case) tj = j for each j.
This can be shown to be a quadratic function i.e. in the form an2 + bn
+ c.
The “average case” for the insertion sort would perhaps be when t j ~
j/2 for each j. This would also give a quadratic function where aavg ~
Class Exercise
Analyse the efficiency (best, worst & average case) of the Bubble Sort
algorithm below:
n = length(A) ‘A is a zero based array
do
newn = 0
for i = 1 to n-1 do
if A[i-1] > A[i] then
swap(A[i-1], A[i])
newn = i
end if
next i
n = newn
until n = 0
