none
help with insertion sort RRS feed

  • Question

  • Well to put it simply I am newish to programming and I have been asked to program an insertion sort (that sorts random integers) but don’t fully understand how, can someone post an example and an explanation so that I can have a go myself. Also I have noticed there is no sample in the forum.

    Sunday, November 7, 2010 3:20 AM

Answers

  • 'Insertion Sort Algorithm from Wikipedia programmed for Small Basic with echoed instructions to screen

    Sub PrintList
      TextWindow.WriteLine("")
      TextWindow.Write("current order : ")
      For l = 1 To Array.GetItemCount(A) - 1
        TextWindow.Write(A[l] + ", ")
      EndFor
      TextWindow.WriteLine(A[l])
    EndSub

    'data
    'sample numbers from wikipedia
    A = "1=5;2=7;3=0;4=3;5=4;6=2;7=6;8=1;"

    'or create a random list of random numbers
    'For d = 1 To Math.GetRandomNumber(10)+10 'between 10-20 indexes
    '  A[d] = Math.GetRandomNumber(100)
    'EndFor
    PrintList()

    'insertion sort algorithm
    'basically it takes a list of numbers and goes from left to
    'right through the list of values, comparing the indexes, two at a time.
    'the current value you are trying to insert is copied to a variable(value)
    'now we can modify the value in that index without losing the original data.
    'if the value on the right(value) is smaller than the value to the left(A[j])
    'the value of the left index is copied into the right index(A[j+1] = A[j]) and
    'the current value(value) is rechecked with the next value to the left(j = j -1).
    'this is repeated until the variable value is larger than the value on
    'the left or the variable value is in the leftmost position. the variable(value) is
    'then copied back to the list(A[j + 1] = value), placing it into the proper
    'position(at the index right of A[j], a smaller number, or in the first index A[1])

    For i = 2 To Array.GetItemCount(A) 'start at second position because calculationg first wastes processing time
      value = A[i]
      TextWindow.WriteLine("value to insert = " + value)
      j = i - 1 'look to the position left of the current position
      done = "false"
      While (done = "false")
        If (A[j] > value) Then
          TextWindow.WriteLine("A[j] > value ===> " + A[j] + " > " + value + ", copy " +  A[j] + " from index " + j + " to index " + (j+1))
          A[j + 1] = A[j]
          j = j - 1 'look to the position left of the current position
          If (j <= 0) Then
            TextWindow.WriteLine("value is at first index, stop comparing")
            done = "true"
          EndIf
        Else
          TextWindow.WriteLine("A[j] <= value ===> " + A[j] + " <= " + value + ", stop comparing, new index = " + (j+1))
          done = "true"
        EndIf
      EndWhile
      A[j + 1] = value
      PrintList() 
    EndFor

    • Marked as answer by CM375508 Tuesday, November 9, 2010 6:44 PM
    Tuesday, November 9, 2010 3:11 PM

All replies

  • You can find the algorithm and description on Wikipedia .  No point repeating this explanation here.

    To start, first create a test array of say about 10 unsorted integers or even the example with 8 integers found on the Wikipedia site, then try to code the sorting algorithm to work on this.  Add plenty of 'debug' TextWindow.WriteLine statements to check what is happening at each step of the sort.

    You will need arrays , For and probably While loops as well as If Else EndIf statements.  If you are not sure about using these in SmallBasic, then start by writing small programs to get comfortable with these first.

    Post your code so far and any problems you have to get more specific help.

    Sunday, November 7, 2010 11:19 AM
    Moderator
  • list[1] = 5 list[2] = 65 list[3] = 10 list[4] = 15 list[5] = 8 list[6] = 73 list[7] = 0 list[8] = 75 list[9] = 90 list[10] = 32 passes = 0 TextWindow.Writeline("pass " + passes +": " + list[1] + ", " + list[2] + ", " + list[3] + ", " + list[4] + ", " + list[5] + ", " + list[6] + ", " + list[7] + ", " + list[8] + ", " + list[9] + ", " + list[10]) For x = 1 To 10 sort[x] = "" EndFor sort[1] = list[1] For a = 1 To 10 If list[a+1] < sort[a] Then temp = sort[a] list[a+1] = sort[a] sort[a+1] = temp endif passes = passes + 1 TextWindow.Writeline("pass " + passes +": " + sort[1] + ", " + sort[2] + ", " + sort[3] + ", " + sort[4] + ", " + sort[5] + ", " + sort[6] + ", " + sort[7] + ", " + sort[8] + ", " + sort[9] + ", " + sort[10]) endfor
    Tuesday, November 9, 2010 11:52 AM
  • sorry for the poor code i tryed to paste it directly but it went weird, i dont know whats wrong with it
    Tuesday, November 9, 2010 11:57 AM
  • 'Insertion Sort Algorithm from Wikipedia programmed for Small Basic with echoed instructions to screen

    Sub PrintList
      TextWindow.WriteLine("")
      TextWindow.Write("current order : ")
      For l = 1 To Array.GetItemCount(A) - 1
        TextWindow.Write(A[l] + ", ")
      EndFor
      TextWindow.WriteLine(A[l])
    EndSub

    'data
    'sample numbers from wikipedia
    A = "1=5;2=7;3=0;4=3;5=4;6=2;7=6;8=1;"

    'or create a random list of random numbers
    'For d = 1 To Math.GetRandomNumber(10)+10 'between 10-20 indexes
    '  A[d] = Math.GetRandomNumber(100)
    'EndFor
    PrintList()

    'insertion sort algorithm
    'basically it takes a list of numbers and goes from left to
    'right through the list of values, comparing the indexes, two at a time.
    'the current value you are trying to insert is copied to a variable(value)
    'now we can modify the value in that index without losing the original data.
    'if the value on the right(value) is smaller than the value to the left(A[j])
    'the value of the left index is copied into the right index(A[j+1] = A[j]) and
    'the current value(value) is rechecked with the next value to the left(j = j -1).
    'this is repeated until the variable value is larger than the value on
    'the left or the variable value is in the leftmost position. the variable(value) is
    'then copied back to the list(A[j + 1] = value), placing it into the proper
    'position(at the index right of A[j], a smaller number, or in the first index A[1])

    For i = 2 To Array.GetItemCount(A) 'start at second position because calculationg first wastes processing time
      value = A[i]
      TextWindow.WriteLine("value to insert = " + value)
      j = i - 1 'look to the position left of the current position
      done = "false"
      While (done = "false")
        If (A[j] > value) Then
          TextWindow.WriteLine("A[j] > value ===> " + A[j] + " > " + value + ", copy " +  A[j] + " from index " + j + " to index " + (j+1))
          A[j + 1] = A[j]
          j = j - 1 'look to the position left of the current position
          If (j <= 0) Then
            TextWindow.WriteLine("value is at first index, stop comparing")
            done = "true"
          EndIf
        Else
          TextWindow.WriteLine("A[j] <= value ===> " + A[j] + " <= " + value + ", stop comparing, new index = " + (j+1))
          done = "true"
        EndIf
      EndWhile
      A[j + 1] = value
      PrintList() 
    EndFor

    • Marked as answer by CM375508 Tuesday, November 9, 2010 6:44 PM
    Tuesday, November 9, 2010 3:11 PM
  • thanks
    Tuesday, November 9, 2010 6:40 PM