Author Topic: Need help with Shell Sort  (Read 5096 times)

nobody

  • Guest
Need help with Shell Sort
« on: November 18, 2004, 10:03:20 PM »
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:

Code:

(N = array size)
Gap = n/2
I=Gap
J=I-Gap

while(Gap >0)
  while(I    while(J>0 && A[J] > A[J+Gap]
        swap (A[J], A[J+Gap])
    J=J-Gap
  I=I+1
Gap=Gap/2




So far I have come up with this but don't know where to go:

Code:

N times 16 dd 0; array size
Gap dd 0
I dd 0
J dd 0

mov eax,16
cdq
mov ebx, 2
idiv ebx
mov Gap, eax ;Gap =N/2
mov I, eax ;I=Gap
sub I, eax ;I-Gap
mov J, eax ;J=I-Gap

while:
   cmp Gap, 0
   jg nextwhile
   jz end

nextwhile:
   mov eax, N
   cmp I, eax
   jl ?(haven't got this far)

innerwhile:


end:





If somone could please look at this and see if I'm track and offer some suggestions I would appreciate it. Really stuck as to where to go. Also, is the original algorithm correct? Just want to verify this. Thanks again for the help.

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2384
  • Country: us
Re: Need help with Shell Sort
« Reply #1 on: November 19, 2004, 05:31:48 PM »
> 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

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2384
  • Country: us
Re: Need help with Shell Sort
« Reply #2 on: November 22, 2004, 08:21:56 PM »


discussion of various sort algorithms... (I was thinking of qsort when I said I thought you were supposed to be swapping sub-lists)... their shell sort C code differs slightly from the pseudo-code you posted - this one *does* make sense to me... Have a look, if you're still working on this...

Best,
Frank