Insertion Sort with sentinel

This code has been declared by its author to be Public Domain code.

Insertion Sort with sentinel by Floyd

2002

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.

; 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 : t\Index = MinInt ; sentinel, the smallest integer

For n = 1 To 15 : t = New Item : t\Index = 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=Item\Index : p = Before Item
		While temp < p\Index
			p = Before p
		Wend
		Insert Item After p
	Forever
	
End Function

;=======================================================

Function ShowData( )
	For a.Item = Each Item
		Write a\Index+" "
	Next
	Print : Print
End Function

Comments

None.

Code Archives Forum