> I'm stuck on a Shell Sort and have so far come up with some code (using NASM)
> but don't know where to go from here. I found this Shell Sort algorithm:
I'm not up on sort algorithms, and my brain's not "sharp" enough right now to figure it out. The only sort I've actually implemented in asm is bubble-sort (kind of a joke, but in fact, for smallish arrays, bubble-sort works fine). So I'm not sure, but I think this might *not* be right...
> Code:
>
> (N = array size)
> Gap = n/2
> I=Gap
> J=I-Gap
This would make the initial J = 0. Is that what we want? Maybe... but then we subtract Gap from it again, making it negative (or large positive)... That doesn't seem right.
> while(Gap >0)
> while(I> while(J>0 && A[J] > A[J+Gap]
The "J>0" is going to skip the first element of our array - that can't be right. The comparison between elements is okay, but... what if we wanted to sort 'em in reverse order? (or some other comparison... third word in a string, or whatever?) A "good" sort routine would take, as a parameter, the address of a "callback" function to do the actual comparison - taking two pointers to generic "data", and returning a "flag" (carry flag, probably?) saying whether they need to be swapped or not. You may want to leave that until later... get it working with a "plain" compare first...
> swap (A[J], A[J+Gap])
This appears to swap just the two array elements. My recollection is that Shell sort is supposed to swap entire "sub-lists" - I may be thinking of a different sort algorithm...
> J=J-Gap
This looks suspicious to me. I don't see how starting with zero, and decrementing by Gap is going to give sensible values. I may be missing something.
> I=I+1
> Gap=Gap/2
Of course, you need to get the algorithm right before you start coding! Is this "homework"? If so, and the algorithm was given with the assignment, it's probably right and I'm probably wrong. Otherwise, I'd re-check that. If you just need the routine, it might be easier to "find" something that could be adapted to your needs - translated to Nasm syntax, if necessary. I wonder if the "Optimization Manuals" would have an example? Google would certainly find something. Writing it from scratch would be more educational, regardless of whether it's formal homework or not, of course!
I've got a C program - came as an example with MSC 6 - that does a "graphical" comparison of various sort algorithms. I've often thought that translating it to asm would be an interesting "exercise" - too lazy to have done anything with it...
> So far I have come up with this but don't know where to go:
I don't either, but I've got some comments anyway :)
> Code:
>
> N times 16 dd 0; array size
Are you making a space for the array itself here? Or declaring a variable containing the array size? I should think you'd want both... something like...
the_array times 16 dd 0 ; or the actual values
array_size dd 16 ; "[array_size]" is "N"
For a "reusable" routine, you'd want the size to be passed as a parameter, not "hard-coded", of course.
> Gap dd 0
> I dd 0
> J dd 0
>
> mov eax,16
> cdq
> mov ebx, 2
> idiv ebx
This does a signed divide. If your array size gets to be greater than 2G, this isn't going to do what you want. This probably isn't going to cause any immediate problem, but logically, the size would never be negative, so an unsigned divide would be better, I would think. A divide by two can easily be accomplished by "shr eax, 1". Besides being faster and shorter, this would have the advantage of not trashing ebx and edx. Either method is going to "truncate" an "odd" array size. With the array size a power of two, this'll never happen, but think about what you want to do if it *is* odd - don't want to leave the last element out of our sort!
> mov Gap, eax ;Gap =N/2
> mov I, eax ;I=Gap
> sub I, eax ;I-Gap
> mov J, eax ;J=I-Gap
All four of these lines (and some following ones) have got a "syntax error". You want "[Gap}", etc. Remember that in Nasm syntax, "myvar" is the address/offset of the variable, "[myvar]" is the contents.
I don't think this does quite what the pseudo-code above says. If we start with 16, eax is 8. We put it in [Gap]... okay... then becomes 8, and subtracting 8 leaves 0 in ... I guess that's okay. Then 8 goes in [J]... that may be correct, but it isn't what the pseudo-code, or the comment, says...
> while:
> cmp Gap, 0
> jg nextwhile
> jz end
The "jg nextwhile" doesn't do anything useful. If you just "jz end", it'll fall through to "nextwhile". "jg" is a signed comparison - since "[Gap}" is never going to be negative (I don't think...), "ja" would have been better anyway.
>
> nextwhile:
> mov eax, N
> cmp I, eax
"[N]" and ""...
> jl ?(haven't got this far)
Mmmm, probably want to fall through if it's less (or "below"... again, "jl" is signed, "jb" is unsigned). Probably want to do something like "jae finished" here. "" should never be above "[N]", so just "je" (=="jz") would do, I think - "jae" won't hurt...
> innerwhile:
The pseudo-code says that if J>0 and if the two elements need to be swapped, we swap 'em and then subtract "[Gap}" from J again. If either of these are not true, we increment "" and go again (without re-initializing J?), until I=N, then halve Gap, and go again (without re-initializing I?)... I may be misreading the pseudo-code - I don't see how this is going to work! As I said, my thinking's a bit fuzzy, and I'm too lazy to look it up. If I can get "inspired", I'll try to get into it - I need a decent sort for my own "arsenal" anyway... If it's homework, I hope it isn't due soon! :)
Best,
Frank
