Qbasicnews.com May 11, 2021, 10:16:03 PM  Pages: Author Topic: Homework crashes, I can't figure out why  (Read 2411 times)
wallace
Wandering Guru   Posts: 368   « on: February 18, 2006, 11:55:41 AM »

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. Logged

f you play a Microsoft CD backwards you can hear demonic voices.  The scary part is that if you play it forwards it installs Windows.
RyanKelly
Forum Regular  Posts: 109   « Reply #1 on: February 18, 2006, 12:39:36 PM »

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 Logged
wallace
Wandering Guru   Posts: 368   « Reply #2 on: February 18, 2006, 12:44:58 PM »

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

f you play a Microsoft CD backwards you can hear demonic voices.  The scary part is that if you play it forwards it installs Windows.
RyanKelly
Forum Regular  Posts: 109   « Reply #3 on: February 18, 2006, 12:49:42 PM »

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. Logged
 Pages: