flat assembler
Message board for the users of flat assembler.

Index > Compiler Internals > Need some help with Shell Sort

Author
Thread Post new topic Reply to topic
pityocamptes



Joined: 18 Nov 2004
Posts: 3
pityocamptes
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.
Post 18 Nov 2004, 22:00
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
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.
Post 18 Nov 2004, 22:21
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
pityocamptes



Joined: 18 Nov 2004
Posts: 3
pityocamptes
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!
Post 18 Nov 2004, 23:18
View user's profile Send private message Reply with quote
JohnFound



Joined: 16 Jun 2003
Posts: 3502
Location: Bulgaria
JohnFound
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.
Post 19 Nov 2004, 06:52
View user's profile Send private message Visit poster's website ICQ Number Reply with quote
pityocamptes



Joined: 18 Nov 2004
Posts: 3
pityocamptes
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
                                 jg  next2               ;if > then jump to next2
                                 jle endwhile3           ;if <= then jump to endwhile3
                                            
                            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!
Post 19 Nov 2004, 22:25
View user's profile Send private message Reply with quote
Display posts from previous:
Post new topic Reply to topic

Jump to:  


< Last Thread | Next Thread >
Forum Rules:
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
You cannot attach files in this forum
You can download files in this forum


Copyright © 1999-2020, Tomasz Grysztar. Also on GitHub, YouTube, Twitter.

Website powered by rwasa.