Answered by:
help with insertion sort
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.
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 1020 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
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.

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


'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 1020 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
