Title : Insertion Sort with sentinel
Author : Floyd
Posted : 1+ years ago
Description : This example shows a variant of Insertion Sort.
It uses a special element to mark the beginning of the list. The idea is that there is no need to check for running off the end of the list.
When using this remember that the first element is not real data. In many situations you can just ignore this. The corresponding image/entity will be far off-screen or out of range so Blitz won't draw anything.
Note: this is an old post. I have just made a slight edit of MinInt for clarity. Code : ; Example of Insertion Sort using a sentinel.
; This is a dummy item which marks the start of the list.
; Use one of the following as the sentinel:
MinStr$ = ""
MinInt% = -(2^31) ; This is $80000000
MinFlt# = -2 * ( 2^127 - 2^103 )
; Example uses integers. If this changes then change temp to match.
Type Item
Field Index% ; integer for this example
End Type
t.Item = New Item : tIndex = MinInt ; sentinel, the smallest integer
For n = 1 To 15 : t = New Item : tIndex = Rand(9) : Next ; the actual data
ShowData
InsertionSortSentinel
ShowData
WaitKey
;=======================================================
; Needs a sentinel, a guaranteed first item.
; This simplifies and speeds up the sort.
Function InsertionSortSentinel()
Local Item.Item, NextItem.Item, p.Item
Local temp% ; must be same type as the sort field.
NextItem=After After First Item
Repeat
If NextItem = Null Then Return
Item = NextItem : NextItem=After NextItem
temp=ItemIndex : p = Before Item
While temp < pIndex
p = Before p
Wend
Insert Item After p
Forever
End Function
;=======================================================
Function ShowData( )
For a.Item = Each Item
Write aIndex+" "
Next
Print : Print
End Function
