Chapter 8
Sorting
All the sorting algorithms in this chapter use data structures of a specific type
to demonstrate sorting, e.g. a 32 bit integer is often used as its associated
operations (e.g. <, >, etc) are clear in their behaviour.
The algorithms discussed can easily be translated into generic sorting algo-
rithms within your respective language of choice.
8.1 Bubble Sort
One of the most simple forms of sorting is that of comparing each item with
every other item in some list, however as the description may imply this form
of sorting is not particularly eÆecient O(n2 ). In it’s most simple form bubble
sort can be implemented as two loops.
1) algorithm BubbleSort(list)
2) Pre: list 6= ;
3) Post: list has been sorted into values of ascending order
4) for i √ 0 to [Link] ° 1
5) for j √ 0 to [Link] ° 1
6) if list[i] < list[j]
7) Swap(list[i], list[j])
8) end if
9) end for
10) end for
11) return list
12) end BubbleSort
8.2 Merge Sort
Merge sort is an algorithm that has a fairly e±cient space time complexity -
O(n log n) and is fairly trivial to implement. The algorithm is based on splitting
a list, into two similar sized lists (lef t, and right) and sorting each list and then
merging the sorted lists back together.
Note: the function MergeOrdered simply takes two ordered lists and makes
them one.
63
CHAPTER 8. SORTING 64
Figure 8.1: Bubble Sort Iterations
1) algorithm Mergesort(list)
2) Pre: list 6= ;
3) Post: list has been sorted into values of ascending order
4) if [Link] = 1 // already sorted
5) return list
6) end if
7) m √ [Link] / 2
8) lef t √ list(m)
9) right √ list([Link] ° m)
10) for i √ 0 to lef [Link]°1
11) lef t[i] √ list[i]
12) end for
13) for i √ 0 to [Link]°1
14) right[i] √ list[i]
15) end for
16) lef t √ Mergesort(lef t)
17) right √ Mergesort(right)
18) return MergeOrdered(lef t, right)
19) end Mergesort
CHAPTER 8. SORTING 65
Figure 8.2: Merge Sort Divide et Impera Approach
8.3 Quick Sort
Quick sort is one of the most popular sorting algorithms based on divide et
impera strategy, resulting in an O(n log n) complexity. The algorithm starts by
picking an item, called pivot, and moving all smaller items before it, while all
greater elements after it. This is the main quick sort operation, called partition,
recursively repeated on lesser and greater sub lists until their size is one or zero
- in which case the list is implicitly sorted.
Choosing an appropriate pivot, as for example the median element is funda-
mental for avoiding the drastically reduced performance of O(n2 ).
CHAPTER 8. SORTING 66
Figure 8.3: Quick Sort Example (pivot median strategy)
1) algorithm QuickSort(list)
2) Pre: list 6= ;
3) Post: list has been sorted into values of ascending order
4) if [Link] = 1 // already sorted
5) return list
6) end if
7) pivot √MedianValue(list)
8) for i √ 0 to [Link]°1
9) if list[i] = pivot
10) [Link](list[i])
11) end if
12) if list[i] < pivot
13) [Link](list[i])
14) end if
15) if list[i] > pivot
16) [Link](list[i])
17) end if
18) end for
19) return Concatenate(QuickSort(less), equal, QuickSort(greater))
20) end Quicksort
CHAPTER 8. SORTING 67
8.4 Insertion Sort
Insertion sort is a somewhat interesting algorithm with an expensive runtime of
O(n2 ). It can be best thought of as a sorting scheme similar to that of sorting
a hand of playing cards, i.e. you take one card and then look at the rest with
the intent of building up an ordered set of cards in your hand.
Figure 8.4: Insertion Sort Iterations
1) algorithm Insertionsort(list)
2) Pre: list 6= ;
3) Post: list has been sorted into values of ascending order
4) unsorted √ 1
5) while unsorted < [Link]
6) hold √ list[unsorted]
7) i √ unsorted ° 1
8) while i ∏ 0 and hold < list[i]
9) list[i + 1] √ list[i]
10) i√i°1
11) end while
12) list[i + 1] √ hold
13) unsorted √ unsorted + 1
14) end while
15) return list
16) end Insertionsort
CHAPTER 8. SORTING 68
8.5 Shell Sort
Put simply shell sort can be thought of as a more e±cient variation of insertion
sort as described in §8.4, it achieves this mainly by comparing items of varying
distances apart resulting in a run time complexity of O(n log 2 n).
Shell sort is fairly straight forward but may seem somewhat confusing at
first as it diÆers from other sorting algorithms in the way it selects items to
compare. Figure 8.5 shows shell sort being ran on an array of integers, the red
coloured square is the current value we are holding.
1) algorithm ShellSort(list)
2) Pre: list 6= ;
3) Post: list has been sorted into values of ascending order
4) increment √ [Link] / 2
5) while increment 6= 0
6) current √ increment
7) while current < [Link]
8) hold √ list[current]
9) i √ current ° increment
10) while i ∏ 0 and hold < list[i]
11) list[i + increment] √ list[i]
12) i° = increment
13) end while
14) list[i + increment] √ hold
15) current √ current + 1
16) end while
17) increment / = 2
18) end while
19) return list
20) end ShellSort
8.6 Radix Sort
Unlike the sorting algorithms described previously radix sort uses buckets to
sort items, each bucket holds items with a particular property called a key.
Normally a bucket is a queue, each time radix sort is performed these buckets
are emptied starting the smallest key bucket to the largest. When looking at
items within a list to sort we do so by isolating a specific key, e.g. in the example
we are about to show we have a maximum of three keys for all items, that is
the highest key we need to look at is hundreds. Because we are dealing with, in
this example base 10 numbers we have at any one point 10 possible key values
0..9 each of which has their own bucket. Before we show you this first simple
version of radix sort let us clarify what we mean by isolating keys. Given the
number 102 if we look at the first key, the ones then we can see we have two of
them, progressing to the next key - tens we can see that the number has zero
of them, finally we can see that the number has a single hundred. The number
used as an example has in total three keys:
CHAPTER 8. SORTING 69
Figure 8.5: Shell sort
CHAPTER 8. SORTING 70
1. Ones
2. Tens
3. Hundreds
For further clarification what if we wanted to determine how many thousands
the number 102 has? Clearly there are none, but often looking at a number as
final like we often do it is not so obvious so when asked the question how many
thousands does 102 have you should simply pad the number with a zero in that
location, e.g. 0102 here it is more obvious that the key value at the thousands
location is zero.
The last thing to identify before we actually show you a simple implemen-
tation of radix sort that works on only positive integers, and requires you to
specify the maximum key size in the list is that we need a way to isolate a
specific key at any one time. The solution is actually very simple, but its not
often you want to isolate a key in a number so we will spell it out clearly
here. A key can be accessed from any integer with the following expression:
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 diÆerent algorithms for sorting
lists, some are very e±cient (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 e±ciency,
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 e±cient, 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 <
p 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 7810 has a binary
representation of 10011102 .
Table 9.1 shows the algorithm trace when the number to convert to binary
is 74210 .
72
CHAPTER 9. NUMERIC 73
1) algorithm ToBinary(n)
2) Pre: n ∏ 0
3) Post: n has been converted into its base 2 representation
4) while n > 0
5) [Link](n % 2)
6) n √ n/2
7) end while
8) return Reverse(list)
9) end ToBinary
n list
742 {0}
371 { 0, 1 }
185 { 0, 1, 1 }
92 { 0, 1, 1, 0 }
46 { 0, 1, 1, 0, 1 }
23 { 0, 1, 1, 0, 1, 1 }
11 { 0, 1, 1, 0, 1, 1, 1 }
5 { 0, 1, 1, 0, 1, 1, 1, 1 }
2 { 0, 1, 1, 0, 1, 1, 1, 1, 0 }
1 { 0, 1, 1, 0, 1, 1, 1, 1, 0, 1 }
Table 9.1: Algorithm trace of ToBinary
9.3 Attaining the greatest common denomina-
tor of two numbers
A fairly routine problem in mathematics is that of finding the greatest common
denominator of two integers, what we are essentially after is the greatest number
which is a multiple of both, e.g. the greatest common denominator of 9, and
15 is 3. One of the most elegant solutions to this problem is based on Euclid’s
algorithm that has a run time complexity of O(n2 ).
1) algorithm GreatestCommonDenominator(m, n)
2) Pre: m and n are integers
3) Post: the greatest common denominator of the two integers is calculated
4) if n = 0
5) return m
6) end if
7) return GreatestCommonDenominator(n, m % n)
8) end GreatestCommonDenominator
CHAPTER 9. NUMERIC 74
9.4 Computing the maximum value for a num-
ber of a specific base consisting of N digits
This algorithm computes the maximum value of a number for a given number
of digits, e.g. using the base 10 system the maximum number we can have
made up of 4 digits is the number 999910 . Similarly the maximum number that
consists of 4 digits for a base 2 number is 11112 which is 1510 .
The expression by which we can compute this maximum value for N digits
is: B N ° 1. In the previous expression B is the number base, and N is the
number of digits. As an example if we wanted to determine the maximum value
for a hexadecimal number (base 16) consisting of 6 digits the expression would
be as follows: 166 ° 1. The maximum value of the previous example would be
represented as F F F F F F16 which yields 1677721510 .
In the following algorithm numberBase should be considered restricted to
the values of 2, 8, 9, and 16. For this reason in our actual implementation
numberBase has an enumeration type. The Base enumeration type is defined
as:
Base = {Binary √ 2, Octal √ 8, Decimal √ 10, Hexadecimal √ 16}
The reason we provide the definition of Base is to give you an idea how this
algorithm can be modelled in a more readable manner rather than using various
checks to determine the correct base to use. For our implementation we cast the
value of numberBase to an integer, as such we extract the value associated with
the relevant option in the Base enumeration. As an example if we were to cast
the option Octal to an integer we would get the value 8. In the algorithm listed
below the cast is implicit so we just use the actual argument numberBase.
1) algorithm MaxValue(numberBase, n)
2) Pre: numberBase is the number system to use, n is the number of digits
3) Post: the maximum value for numberBase consisting of n digits is computed
4) return Power(numberBase, n) °1
5) end MaxValue
9.5 Factorial of a number
Attaining the factorial of a number is a primitive mathematical operation. Many
implementations of the factorial algorithm are recursive as the problem is re-
cursive in nature, however here we present an iterative solution. The iterative
solution is presented because it too is trivial to implement and doesn’t suÆer
from the use of recursion (for more on recursion see §C).
The factorial of 0 and 1 is 0. The aforementioned acts as a base case that we
will build upon. The factorial of 2 is 2§ the factorial of 1, similarly the factorial
of 3 is 3§ the factorial of 2 and so on. We can indicate that we are after the
factorial of a number using the form N ! where N is the number we wish to
attain the factorial of. Our algorithm doesn’t use such notation but it is handy
to know.
CHAPTER 9. NUMERIC 75
1) algorithm Factorial(n)
2) Pre: n ∏ 0, n is the number to compute the factorial of
3) Post: the factorial of n is computed
4) if n < 2
5) return 1
6) end if
7) f actorial √ 1
8) for i √ 2 to n
9) f actorial √ f actorial § i
10) end for
11) return f actorial
12) end Factorial
9.6 Summary
In this chapter we have presented several numeric algorithms, most of which
are simply here because they were fun to design. Perhaps the message that
the reader should gain from this chapter is that algorithms can be applied to
several domains to make work in that respective domain attainable. Numeric
algorithms in particular drive some of the most advanced systems on the planet
computing such data as weather forecasts.
Chapter 10
Searching
10.1 Sequential Search
A simple algorithm that search for a specific item inside a list. It operates
looping on each element O(n) until a match occurs or the end is reached.
1) algorithm SequentialSearch(list, item)
2) Pre: list 6= ;
3) Post: return index of item if found, otherwise °1
4) index √ 0
5) while index < [Link] and list[index] 6= item
6) index √ index + 1
7) end while
8) if index < [Link] and list[index] = item
9) return index
10) end if
11) return °1
12) end SequentialSearch
10.2 Probability Search
Probability search is a statistical sequential searching algorithm. In addition to
searching for an item, it takes into account its frequency by swapping it with
it’s predecessor in the list. The algorithm complexity still remains at O(n) but
in a non-uniform items search the more frequent items are in the first positions,
reducing list scanning time.
Figure 10.1 shows the resulting state of a list after searching for two items,
notice how the searched items have had their search probability increased after
each search operation respectively.
76
CHAPTER 10. SEARCHING 77
Figure 10.1: a) Search(12), b) Search(101)
1) algorithm ProbabilitySearch(list, item)
2) Pre: list 6= ;
3) Post: a boolean indicating where the item is found or not;
in the former case swap founded item with its predecessor
4) index √ 0
5) while index < [Link] and list[index] 6= item
6) index √ index + 1
7) end while
8) if index ∏ [Link] or list[index] 6= item
9) return false
10) end if
11) if index > 0
12) Swap(list[index], list[index ° 1])
13) end if
14) return true
15) end ProbabilitySearch
10.3 Summary
In this chapter we have presented a few novel searching algorithms. We have
presented more e±cient searching algorithms earlier on, like for instance the
logarithmic searching algorithm that AVL and BST tree’s use (defined in §3.2).
We decided not to cover a searching algorithm known as binary chop (another
name for binary search, binary chop usually refers to its array counterpart) as
CHAPTER 10. SEARCHING 78
the reader has already seen such an algorithm in §3.
Searching algorithms and their e±ciency largely depends on the underlying
data structure being used to store the data. For instance it is quicker to deter-
mine whether an item is in a hash table than it is an array, similarly it is quicker
to search a BST than it is a linked list. If you are going to search for data fairly
often then we strongly advise that you sit down and research the data structures
available to you. In most cases using a list or any other primarily linear data
structure is down to lack of knowledge. Model your data and then research the
data structures that best fit your scenario.