locked
Help regarding Shell Sorting RRS feed

  • 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)
      numbers[i] = TextWindow.ReadNumber()
    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

    Please help me


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


    • Edited by 4mir '- 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 array
    For i = 0 To MaxSize - 1
      TextWindow.Write(i+1 + " -> ")
      numbers[i] = TextWindow.ReadNumber()
    EndFor

    increment = 3
    i = 0

    While 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
        
      EndWhile
    EndWhile

    For 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
    Answerer
  • 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
    Answerer
  • 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).

    Your version:

        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 litdev 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