Homework crashes, I can't figure out why

[wallace]

Code:

declare sub makearray(size as integer)
declare sub shellsort(a() as integer, length as integer, outpt() as integer)
declare sub shellsortphase(a() as integer, length as integer, gap as integer)

REDIM SHARED testarray(0) as integer
redim shared outputarray(0) as integer
dim t as double   'timing variable (64 bit float)

t = timer
makearray 10000
for times = 0 to 1000
    shellsort @testarray(0), 10000, @outputarray(0)
next
print "Sort of 10000 integers took " + STR$((timer - t)/1000) + "seconds."
sleep
end

sub shellsortphase (a() as integer, length as integer, gap as integer)
      for i = gap to length
         value = a(i)
         j = i - gap
         while j >= 0 AND a(j) > value
            a(j + gap) = a(j)
            j = j - gap
         wend
         a(j + gap) = value
      next
end sub

sub shellsort(a() as integer, length as integer, outpt() as integer)
    'need to have a second array so that I don't need to rebuild the array every time which would
    '   cut down on accuracy
    static gaps(10) as integer
    gaps(0) = 1
    gaps(1) = 2
    gaps(2) = 5
    gaps(3) = 13
    gaps(4) = 34
    gaps(5) = 89
    gaps(6) = 233
    gaps(7) = 610
    gaps(8) = 1597
    gaps(9) = 4181
    gaps(10) = 10946
    for i = 0 TO length
        outpt(i) = a(i)    'copy array so that I can loop this multiple times
    next
    for sizeIndex = 10 TO 0 STEP -1
        shellsortphase @outpt(0), length, gaps(sizeIndex)
    next
end sub

sub makearray(size as integer)
    REDIM testarray(size) as integer
    redim outputarray(size) as integer    'resizes and sets all values to 0
    FOR i = 0 to size
        testarray(i) = RND * 2147483647        'range is all valid numbers for a 32 bit integer
    NEXT
end sub

This shell sort doesn't work. It crashes after about 5 passes. I've checked all of the index values and they are all fine. I've narrowed the problem down to shellsortphase, but other than that I'm stumped. It does seem to work for smaller sized arrays.

[RyanKelly]

Code:

sub shellsortphase (a() as integer, length as integer, gap as integer)
      for i = gap to length
         value = a(i)
         j = i - gap
         while j >= 0 AND a(j) > value
            a(j + gap) = a(j)
************j = j - gap****************
* ON THE SECOND PASS, WHEN J=3, gap=4181.
* j-gap = -4178 !
* This is causing a memory fault during execution.
***************************************

         wend
         a(j + gap) = value
      next
end sub

I'm not familiar with many academic algorythms, so I'm not clear on how a shell sort is suppose to function, but I am sure that the line
j= j - gap is triggering an exception when the loop tests the condition a(j)>value whenever gap > j.

I suggest recoding the loop this way.

Code:

do while a(j) > value
    a(j + gap) = a(j)
    j = j - gap
    if j<0 then exit do
loop

[wallace]

That is after the index call. When it goes negative the while loop exits.

[RyanKelly]

Both conditions in your while statement get evaluated because you are performing the bitwise AND on the results of the two condtions. See the edit to my first reply.

For a statement such as:
while i>=0 and a(i)>value

fbc.exe produces this assembly language code:

mov eax, dword ptr [_Ii]
test eax, eax
setge al
shr eax, 1
sbb eax, eax
mov ebx, dword ptr [_Ii]
mov ecx, dword ptr [_Ai+ebx*4]
cmp ecx, dword ptr [_VALUEi]
setg cl
shr ecx, 1
sbb ecx, ecx
and eax, ecx


Notice that both calculation are performed every time.