# Help regarding Shell Sorting

• ### General discussion

• Step 1. Initialize

set increment = 3, set i = 0

Step 2. Repeat step 3 to 10 until increment > 0

Step 3. Repeat 4 to 9 until i < MaxSize

Step 4. Set J = I

Step 5. Set temp = numbers[i]

Step 6. Repeat Step 7 and 8 until J >= increment And numbers[j] - increment > temp

Step 7. Set numbers[j] = numbers[j] - increment

Step 8. set j = j - increment

Step 9. Set numbers[j] = temp

Step 10. If increment/2 <> 0 Then Set increment = increment/2

Elseif

increment = 1 then set increment = 0

else

increment = 1

end if

i found this Shell sort algorithm in my brother's book and tried to implement it into Small Basic but there are some problems, i think the else if commands are not working correctly when variable increment become 1 it should be then converted to 0 and the main loop should stop working but it cant seems to work as coded...

HERE IS THE SB CODE

MAX_NUM = 5
'get the user input into array
For i = 0 To MAX_NUM - 1
'numbers[i] = Math.GetRandomNumber(100)
EndFor
i = 0
increment = 3
While(increment > 0)
For i = 0 To MAX_NUM - 1
j = i
temp = numbers[i]
While((j >= increment) And (numbers[j - increment] > temp))
numbers[j] = numbers[j - increment]
j = j - increment
EndWhile
numbers[j] = temp
EndFor
If(increment/2 <> 0) Then
increment = increment/2
ElseIf(increment = 1) Then
increment = 0
Else
increment = 1
EndIf
'debuger
TextWindow.WriteLine(increment)
EndWhile
'print the sorted value
TextWindow.WriteLine("Done with sort")
For i = 0 To MAX_NUM - 1
TextWindow.WriteLine(numbers[i])
EndFor

They say working hard is good but i say working smart is best...

• Edited by Thursday, September 13, 2012 2:46 AM Corrected Mistake
Wednesday, September 12, 2012 5:32 PM

### All replies

• Hi!

There are some things I don't get from that encrypted sort algorithm:

• Where is Step 9?
• Step 8 overrides what was done at Step 7 in relation to Set numbers[j]!
• Assuming until means while!!!
• Assuming numbers[j] - increment means numbers[j - increment]

I tried to follow its logic, but come out w/ an even less working program than yours!  :P

`MaxSize = 3'get the user input into arrayFor i = 0 To MaxSize - 1  TextWindow.Write(i+1 + " -> ")  numbers[i] = TextWindow.ReadNumber()EndForincrement = 3i = 0While increment > 0  While i < MaxSize    j = i    temp = numbers[i]        TextWindow.WriteLine(increment)        While j >= increment And numbers[j - increment] > temp            numbers[j] = numbers[j - increment]      numbers[j] = temp          EndWhile        If increment/2 <> 0 Then      increment = increment/2    ElseIf increment = 1 Then      increment = 0    Else      increment = 1    EndIf      EndWhileEndWhileFor i = 0 To MaxSize - 1  TextWindow.WriteLine(numbers[i])EndFor`

Click on "Propose As Answer" if some post solves your problem or "Vote As Helpful" if some post has been useful to you! (^_^)

Wednesday, September 12, 2012 6:33 PM
• As far as I can see a couple of issues, compared with standard shellsorts:

1] For i = 0 To MAX_NUM - 1 should be For i = increment To MAX_NUM - 1

2] The increment update, I would replace:

If(increment/2 <> 0) Then
increment = increment/2
ElseIf(increment = 1) Then
increment = 0
Else
increment = 1
EndIf

With:

increment = Math.Round(increment/2.2)

Wednesday, September 12, 2012 6:37 PM
• Here it is a thread I published a bubble sort solution:

Sorting Numbers! Emergency!

Click on "Propose As Answer" if some post solves your problem or "Vote As Helpful" if some post has been useful to you! (^_^)

Wednesday, September 12, 2012 6:56 PM
• And a shell ,bubble sort comparison, import QKR631.
Wednesday, September 12, 2012 7:11 PM
• As far as I can see a couple of issues, compared with standard shellsorts:

1] For i = 0 To MAX_NUM - 1 should be For i = increment To MAX_NUM - 1

2] The increment update, I would replace:

If(increment/2 <> 0) Then
increment = increment/2
ElseIf(increment = 1) Then
increment = 0
Else
increment = 1
EndIf

With:

increment = Math.Round(increment/2.2)

It's working now Thanks LitDev but would you care to elaborate on underlined part??? i didn't get that...

They say working hard is good but i say working smart is best...

Thursday, September 13, 2012 2:52 AM
• increment = Math.Round(increment/2.2)

This finds the rounded down integer, dividing increment by 2.2.

I can't remember where I came across this so have to think it through.

The loop ends (sort done) when increment = 0 (all sub sorts completed).

If(increment/2 <> 0) Then
increment = increment/2
ElseIf(increment = 1) Then
increment = 0
Else
increment = 1
EndIf

The first 'If(increment/2 <> 0) Then' is true for all values of increment except 0 and 1, and increment is divided by 2.

If it is 1, then it gets set to 0.

If it is 0 then it gets set to 1, but we should have already finished if it is 0.

So a test program to see the effects:

```For i = 1 To 100
increment = i
If(increment/2 <> 0) Then
increment = increment/2
ElseIf(increment = 1) Then
increment = 0
Else
increment = 1
EndIf

TextWindow.WriteLine(i+" : "+increment+" : "+Math.Floor(i/2.2))
EndFor```

We see a similar, but different reduction in increment using both methods, but also yours creates fractional values for increment!

Now this will cause problems for SmallBasic, since the array indexing is not by integer, but by a string (or key), so x[1] is a different element to x[1.5].

So lets truncate yours to an integer - perhaps assumed by your original pseudo-code.

So we try:

```  If(increment/2 <> 0) Then
increment = Math.Floor(increment/2)
ElseIf(increment = 1) Then
increment = 0
Else
increment = 1
EndIf```

Hey, it works!

EDIT

short answer - when we have done the work looking at it.

In most langauges if you do x/2 (and x is an integer) you get an integer result (rounded down), you have to do x/2.0 to get a fractional (real number) result.  Since SmallBasic doesn't have integer, real etc types, it doesn't do this and x/2 gives a fractional result if x is an odd integer.

To be consistent, perhaps we also should have:

`If(Math.Floor(increment/2) <> 0) Then`
• Edited by Thursday, September 13, 2012 8:20 PM
Thursday, September 13, 2012 6:51 PM
• Thanks Sir.

They say working hard is good but i say working smart is best...

Saturday, September 15, 2012 6:47 AM