7/17/2011
Algorithms
Algorithms are ways of solving problems. There is
a technical definition that basically says an
algorithm is a clear set of instructions which if
followed will lead to a correct problem solution in
a finite amount of time
Sorting is a very important problem and has been
studied extensively. We begin by looking at a
simple sorting algorithm
We build up to the algorithm by starting with
finding the smallest element in an array
Introduction to Algorithms
Finding the smallest element
in an array
Find the Smallest and Make it the First
What if we want to find the smallest element
and put it first in the array?
Well do this by switching it with the first
element
We need to know the index of the smallest
element to do this
A slight modification of our code for finding
the smallest element will let us do this
min = data(1) 'the smallest so far
For k = 2 To lastIndex
'test each element to see if it is the min so far
If data(k) < min Then 'new min found
min = data(k)
End If
Next
Find the smallest element and its index
Switching the Values of Variables
(PROBLEM!!)
Consider the following code:
min = data(1) 'the smallest so far
minIndex = 1
For k = 2 To lastNdx
'test each element to see if it is the min so far
If data(k) < min Then 'new min found
min = data(k)
minIndex = k
End If
Next k
varA = 1
varB = 4
varA = varB
varB = varA
What are the values of varA and varB after I
do this?
7/17/2011
Switching the Values of Variables
Now Using the Array
*** find the smallest element, value and index
min = data(1) 'the smallest so far
minIndex = 1
For k = 2 To lastNdx
'test each element to see if it is the min so far
If data(k) < min Then 'new min found
min = data(k)
minIndex = k
End If
Next
*** exchange the smallest element with the first
temp = data(1)
data(1) = data(minIndex)
data(minIndex) = temp
Doing it right:
varA = 1
varB = 4
temp = varB
varB = varA
varA = temp
What are the values of varA and varB after I
do this?
7
Idea for Sorting
Algorithm picture (1)
Heres an initial array:
Find the smallest element in the array, and
switch it with the first one
Find the smallest element in the rest of the
array, and switch it with the second one
Etc.
This is called selection sort
10
11
The smallest element is in index 3. If we switch it
with the element in index 1, we get:
2
10
11
We now know the first element is the smallest.
9
10
Algorithm picture (2)
Algorithm picture (3)
Looking at elements 2-5, the smallest is in index 5
2
10
11
Lets switch with the element in index 2
2
10
11
Consider elements 3-5. The smallest is in
position 5.
2
10
11
Lets switch with the element in index 3
Now we know the first two are smallest, and are
in the right order.
11
11
10
12
7/17/2011
Algorithm picture (4)
Algorithm Structure
Consider elements 4-5. The smallest is in
position 5.
2
11
10
We want to work on the whole array, then the
array without the first element, then the array
without the second element, etc.
If we work on a whole array of n elements,
thats a loop from 1 to n.
If we work on a whole array minus the first
element, that loop is from 2 to n.
Next we do 3 to n, etc.
Lets switch with the element in index 4
2
10
11
This finishes sorting the array (why?)
13
Loop Setup
14
In general
A loop from 1 to n looks like:
For k = 1 To n
<code>
Next k
Heres a loop from 2 to n:
For k = 2 To n
<code>
Next k
We need a loop that looks like this:
For k = j To n
<code>
Next k
for each j going from 1 to n-1. This we can do
by using another loop!
15
The Nested Loop
16
Heres the Code
For j = 1 To lastNdx 1 start with element j
min = data(j) 'the largest so far
minIndex = j
For k = j + 1 To lastNdx look at elements that follow j
If data(k) < min Then
min = data(k)
minIndex = k
End If
Next k
temp = data(j) exchange the smallest element with element j
data(j) = data(minIndex)
data(minIndex) = temp
Next j
Heres what the structure looks like
For j = 1 To n - 1
For k = j + 1 To n
<code>
Next k
Next j
17
18
7/17/2011
Tricky Bits
Note the -1 and +1 in the loop limits. Getting
those right takes some thought
Does the code work on arrays with just one
element? With two elements? With no
elements? (Nothing to sort, but we want to
avoid a runtime error.) What if the data is
already sorted?
Demo: Simple Sort
19
20
Other Ways of Sorting
Which Method is Best?
There are actually many ways of sorting items
Sorting is very important so people have put a
lot of thought into it
Some well-known methods:
With small data sets, the best method is
usually the easiest one to program
With large data sets, speed becomes an issue
We could measure the time with a stopwatch,
but the essential factor is the functional form
of the time: if n is the length of the list of data,
is the time proportional to n? n log n? n2?
Bubble sort
Quicksort
Heapsort
Mergesort
Bucket sort
21
Comparison of n, n log n, n2
Time for Selection Sort
1800
The number of comparisons of data elements in a
sorting algorithm is usually proportional to the time
On the first loop in Selection Sort, we do n-1
comparisons. The second loop does n-2, etc; the last
loop does 1
So the time is roughly proportional to
(n-1) + (n-2) + + 1 = (n^2 n)/2
The largest power of n is n^2 which dominates the
time for this algorithm
This means Selection Sort is actually too slow to use on
large amounts of data
1600
1400
1200
1000
n^2
n log n
800
22
600
400
200
0
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39
23
24
7/17/2011
Importance of Algorithms
Software Engineering
You now know the basics for programming:
assignment statements, conditionals,
procedures and functions, loops, and arrays
This is like knowing the rules for chess or go
What you have only started to learn are the
tactics and strategies to use these tools
effectively
Algorithms are the tactics for how to
accomplish tasks quickly and correctly
Software engineering is about the strategies to
control the complexity of designing large
programs
Weve been learning a few of these strategies
(e.g. naming conventions, principles of program
structure, requirements and specifications)
Good software engineering allows one person or
a large group to produce a complex program that
is correct and cost-effective
25
26
