D a t a s t r u c t u r e s a n d a L g o r I t h m s Annotated Reference with Examples

key ← (number / keyT oAccess) % 10. As a simple example lets say that we
want to access the tens key of the number 1290, the tens column is key 10 and
so after substitution yields key ← (1290 / 10) % 10 = 9. The next key to
look at for a number can be attained by multiplying the last key by ten working
left to right in a sequential manner. The value of key is used in the following
algorithm to work out the index of an array of queues to enqueue the item into.
1) algorithm Radix(list, maxKeySize)
2)
Pre: list 6= ∅
3)
maxKeySize ≥ 0 and represents the largest key size in the list
4)
Post: list has been sorted
5)
queues ← Queue[10]
6)
indexOf Key ← 1
7)
fori ← 0 to maxKeySize − 1
8)
foreach item in list
9)
queues[GetQueueIndex(item, indexOf Key)].Enqueue(item)
10)
end foreach
11)
list ← CollapseQueues(queues)
12)
ClearQueues(queues)
13)
indexOf Key ← indexOf Key ∗ 10
14)
end for
15)
return list
16) end Radix
Figure 8.6 shows the members of queues from the algorithm described above
operating on the list whose members are 90, 12, 8, 791, 123, and 61, the key we
are interested in for each number is highlighted. Omitted queues in Figure 8.6
mean that they contain no items.
8.7
Summary
Throughout this chapter we have seen many different algorithms for sorting
lists, some are very efficient (e.g. quick sort defined in §8.3), some are not (e.g.

---

CHAPTER 8. SORTING
71
Figure 8.6: Radix sort base 10 algorithm
bubble sort defined in §8.1).
Selecting the correct sorting algorithm is usually denoted purely by efficiency,
e.g. you would always choose merge sort over shell sort and so on. There are
also other factors to look at though and these are based on the actual imple-
mentation. Some algorithms are very nicely expressed in a recursive fashion,
however these algorithms ought to be pretty efficient, e.g. implementing a linear,
quadratic, or slower algorithm using recursion would be a very bad idea.
If you want to learn more about why you should be very, very careful when
implementing recursive algorithms see Appendix C.

---

Chapter 9
Numeric
Unless stated otherwise the alias n denotes a standard 32 bit integer.
9.1
Primality Test
A simple algorithm that determines whether or not a given integer is a prime
number, e.g. 2, 5, 7, and 13 are all prime numbers, however 6 is not as it can
be the result of the product of two numbers that are < 6.
In an attempt to slow down the inner loop the
√
n is used as the upper
bound.
1) algorithm IsPrime(n)
2)
Post: n is determined to be a prime or not
3)
for i ← 2 to n do
4)
for j ← 1 to sqrt(n) do
5)
if i ∗ j = n
6)
return false
7)
end if
8)
end for
9)
end for
10) end IsPrime
9.2
Base conversions
DSA contains a number of algorithms that convert a base 10 number to its
equivalent binary, octal or hexadecimal form. For example 78
10
has a binary
representation of 1001110
2
.
Table 9.1 shows the algorithm trace when the number to convert to binary
is 742
10
.
72

---