While it might look as simple as 1+1=2, sorting routines found on the internet are not always correct. Take shellsort for example, a sorting algorithm which on average is among the best and also simplest. What we see very often at the beginning is something like this:
Code: Select all
max = upperbound \ 2
while max > 0
...
Suppose you have an array with two elements (0..1). The division upperbound \ 2 returns 0 so the next statement while max > 0 prevents those two elements from being sorted. It's very simple, yet we see this A LOT and the error doesn't surface as long as we do test runs with many elements.
So I went back to an old QuickBASIC book to see how a correct Shellsort looks like (I used it a lot in those days):
Code: Select all
sub Shellsort(arr())
n1 = lbound(arr)
n2 = ubound(arr)
max = n2 - n1 + 1
while max > 1
max = max \ 2
do
nswap = false
for i = n1 to n2 - max
j = i + max
if arr(i) > arr(j) then
swap arr(i), arr(j)
nswap = true
end if
next
loop while nswap
wend
end sub
Very simple and very effective. I also ported this code successfully to a Pascal project. Whenever I need to sort a list or array and the type or object doesn't provide one, I implement this Shellsort. No need to go through the hazzle of creating a universal one. ;)