Transcript 4StandardAlgorithms

Higher Grade Computing Studies
4. Standard Algorithms
Linear Search
• This algorithm allows the programmer to search a list (an array)
for a specific item of data.
• Each item in the list is compared with the data being searched
for.
• When a ‘match’ is found then the position (in the array) is
displayed.
1
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Linear Search
• Let's say we have a list of 10 numbers in an array. (The top
number only shows the position of each box in the array).
1
2
3
4
5
6
7
8
9
10
3
64
18
2
64
98
2
100
1
2
• We want to look for the number 64. We can see that it
appears twice on the list, at positions 2 and 5.
2
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Linear Search
1.1 ask for item being searched for
1.2 get item being searched for
1.3 FOR each item in the list
1.4
IF item_in_list = item being searched for THEN
1.5
report position in list
1.6
END IF
1.7 END FOR loop
3
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Counting Occurrences
• This algorithm allows the programmer to count how many times
an item of data appears in a list (an array).
• Each item in the list is compared with the item of data being
counted.
• When a ‘match’ is found, one is added to the total number of
occurrences.
4
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Counting Occurrences
• Let's say we have a list of 10 numbers in an array. (The top
number only shows the position of each box in the array).
1
2
3
4
5
6
7
8
9
10
3
64
18
2
64
98
2
100
1
2
• We want to count how many times the number 2 appears in
the list. We can see that it appears three times in the list.
5
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Counting Occurrences
1.1
1.2
1.3
1.4
1.5
1.6
1.7
1.8
1.9
6
set counter to zero
ask for item being counted
get item being counted
FOR each item in the list
IF item_in_list = item being counted THEN
add 1 to the counter
END IF
END FOR loop
display message showing number of occurrences (counter)
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Finding the Maximum
• This algorithm allows the programmer to find the highest number
in a list (an array).
7
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Counting Occurrences
• Let's say we have a list of 10 numbers in an array. (The top
number only shows the position of each box in the array).
1
2
3
4
5
6
7
8
9
10
3
64
18
2
64
98
2
100
1
2
• We want to find the highest number in the list. As you can
see, it is the number 100.
8
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Counting Occurrences
1.1
1.2
1.3
1.4
1.5
1.6
1.7
9
set ‘largest so far’ to the value of the first item in the list
FOR each of the remaining items
IF current item > largest so far THEN
set ‘largest so far’ = current item
END IF
NEXT item in list
display message showing ‘largest so far’
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Finding the Minimum
• This algorithm allows the programmer to find the lowest number
in a list (an array).
10
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Counting Occurrences
• Let's say we have a list of 10 numbers in an array. (The top
number only shows the position of each box in the array).
1
2
3
4
5
6
7
8
9
10
3
64
18
2
64
98
2
100
1
2
• We want to find the lowest number in the list. As you can
see, it is the number 1.
11
Higher Computing
Software Development
S. McCrossan
Higher Grade Computing Studies
4. Standard Algorithms
Counting Occurrences
1.1
1.2
1.3
1.4
1.5
1.6
1.7
12
set ‘smallest so far’ to the value of the first item in the list
FOR each of the remaining items
IF current item < smallest so far THEN
set ‘smallest so far’ = current item
END IF
NEXT item in list
display message showing ‘smallest so far’
Higher Computing
Software Development
S. McCrossan