flat assembler
Message board for the users of flat assembler. Index > Compiler Internals > Need some help with Shell Sort
Author
 Thread  pityocamptes

Joined: 18 Nov 2004
Posts: 3
pityocamptes 18 Nov 2004, 22:00
Hi, all. Not sure if this is the right forum or not (if not feel free to move). I am using the NASM compiler but am hoping that someone might be able to help me with some code. 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<N)
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. 18 Nov 2004, 22:00  JohnFound Joined: 16 Jun 2003 Posts: 3499 Location: Bulgaria JohnFound 18 Nov 2004, 22:21 Hi. At first, you have to use "[lable]" in order to manipulate the value of the variable: Code:```mov [I], eax ;I=Gap sub [I], eax ;I = I-Gap ; actually you mean: J = I - Gap ; This have to be: mov eax, [I] sub eax, [Gap] mov [J], eax ``` Second: The condition of the second loop looks like: Code:```.while1: cmp [Gap], 0 jle .endwhile1 .while2: mov eax, [I] cmp eax, [N] jge .endwhile2 ; the loop ends when I>=N .while3: ; some more complex condition jxx .endwhile3 ; swap the elements mov eax, [Gap] sub [J], eax jmp .while3 .endwhile3: inc [I] jmp .while2 .endwhile2: sar [Gap], 1 ; Gap = Gap / 2 jmp .while1 .endwhile1: ``` Regards. 18 Nov 2004, 22:21
pityocamptes

Joined: 18 Nov 2004
Posts: 3
pityocamptes 18 Nov 2004, 23:18
Thanks! I have a few other questions just to clarify. I'm confused on what variables I should be using in the first code bloack you show:

Code:
```mov [I], eax  ;I=Gap

sub [I], eax ;I = I-Gap  ; actually you mean: J = I - Gap

; This have to be:
mov eax, [I]
sub  eax, [Gap]
mov [J], eax
```

You added some code after the ";This have to be:" is this how I would set it up - which registers/variables should I use? Also, the while blocks you show is that based off the algorithm I posted or is this a true Shell Sort? The reason I ask is because I wasn't too sure what the Shell Sort algorithm looked like and assumed it is the one I posted. Since I'm sorting an array of filled random numbers I'll have to alter the code a little to read in the arrays. Can you point out which while loops I would set and move the esi pointer for the array? Thanks again for your help! Assembly is really tough! 18 Nov 2004, 23:18  JohnFound Joined: 16 Jun 2003 Posts: 3499 Location: Bulgaria JohnFound 19 Nov 2004, 06:52 pityocamptes wrote:You added some code after the ";This have to be:" is this how I would set it up - which registers/variables should I use? I mean that the instruction "sub [I], eax" in your code actually makes: "I := I - Gap", while according to your pseudo code, you need the operation: "J := I - Gap". So, this last operation, can be done with the instructions I posted after "This have to be" comment. Quote:Also, the while blocks you show is that based off the algorithm I posted or is this a true Shell Sort? The reason I ask is because I wasn't too sure what the Shell Sort algorithm looked like and assumed it is the one I posted. Since I'm sorting an array of filled random numbers I'll have to alter the code a little to read in the arrays. Can you point out which while loops I would set and move the esi pointer for the array? Thanks again for your help! Assembly is really tough! Well, actually I don't know whether it is Shell sort or not. IMHO, Shell sort is not so good to be used on regular basis. Actually I made some tests some time ago and found it slower than "quick sort" for most of the applications. Regards. 19 Nov 2004, 06:52
pityocamptes

Joined: 18 Nov 2004
Posts: 3
pityocamptes 19 Nov 2004, 22:25
Ok. There was some question with others as to the validity of the first Shell Sort algorithm I found. I found a new algorithm and it looks to be good. Here it is:

Code:
```void shellSort(int numbers[], int array_size)
{
int i, j, increment, temp;

increment = 3;
while (increment > 0)
{
for (i=0; i < array_size; i++)
{
j = i;
temp = numbers[i];
while ((j >= increment) && (numbers[j-increment] > temp))
{
numbers[j] = numbers[j - increment];
j = j - increment;
}
numbers[j] = temp;
}
if (increment/2 != 0)
increment = increment/2;
else if (increment == 1)
increment = 0;
else
increment = 1;
}
}
```

Here is my assembly code:

Code:
```Array times 16 dd 0        ;open 16 element array set to zero
N dd 16                   ;set variable N to 16
I dd 0                 ;set variable I to 0
J dd 0                  ;set variable J to 0
Increment dd 3          ;set variable increment to 3
Temp dd 0               ;set variable temp to 0

mov esi, Array               ;set start address of Array to esi
mov edi, [Increment]      ;move increment value to edi

startwhile1:

cmp [edi], 0    ;compares increment to zero
jle end         ;if increment>0 then proceed; if not end

startwhile2:

mov eax, [N]    ;moves value of N into eax
cmp eax, [I]    ;compares I & eax (eax=N)
jle endwhile2   ;jump if less than or equal to endwhile2
mov eax, [I]    ;J=I
mov [J], eax    ;moves eax into J
mov Temp, [esi] ;temp = numbers[I]

startwhile3:

mov eax, [edi]  ;moves edi(Increment) into eax
cmp [J], eax    ;(eax=Increment)
jge next1       ;compares J and edi jumps if >=
jl  endwhile3   ;if < then endwhile

next1:

mov eax, [J]            ;moves value of J into eax
sub [edi], eax          ;subtracts value of eax into edi
mov eax, [esi + edi]    ;moves value into eax from (esi + edi)
cmp eax, [Temp]         ;compares temp value to eax

next2:

mov eax, [J]            ;move the value of J into eax
xchg eax, [esi + edi]   ;exchanges (J) with (J-increment)
mov eax, [J]            J=J-Increment
sub eax, [edi]
mov [J], eax

endwhile3:

mov eax, [Temp]         ;numbers[J] = Temp
mov [J], eax

jmp startwhile3

endwhile2:

inc [I]         ;increment I

if:
mov eax, [edi]  ;increment/2 !=0
shr eax, 1
cmp eax, 0
jg      elseif

mov eax, [edi]  ;increment=increment/2
shr eax, 1
mov [edi], eax

elseif:
mov eax, [edi]  ;if increment==1
cmp eax, 1
jne else

mov [edi], 0

else:

mov [edi], 1

jmp startwhile2

endwhile1:

jmp startwhile1

end:
```

Since I am running out of time to get this done I would REALLY appreciate it if someone could look at this thoroughly and let me know what needs to be changed. Once again I really appreciate the help given so far. Thanks! 19 Nov 2004, 22:25  Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year Oldest FirstNewest First  Jump to: Select a forum Official----------------AssemblyPeripheria General----------------MainTutorials and ExamplesDOSWindowsLinuxUnixMenuetOS Specific----------------MacroinstructionsOS ConstructionIDE DevelopmentProjects and IdeasNon-x86 architecturesHigh Level LanguagesProgramming Language DesignCompiler Internals Other----------------FeedbackHeapTest Area

Forum Rules:
 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot vote in polls in this forumYou cannot attach files in this forumYou can download files in this forum