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

list 6= ∅
3)
Post: list has been sorted into values of ascending order
4)
unsorted ← 1
5)
while unsorted < list.Count
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 efficient 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 differs 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 ← list.Count / 2
5)
while increment 6= 0
6)
current ← increment
7)
while current < list.Count
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: