Insertion Sort

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

Insertion Sort by Floyd

2002

This is particularly fast on data which is "nearly sorted". That is often the case with entities or images. The game loop repeatedly moves things slightly and then sorts them again.

The Index field might be a screen y-coordinate or a world z-coordinate. Or anything else.

Note: I'm editing this so the two sorts are together in the Archive.

; Example of Insertion Sort. For other data types, change the Index
; field and also the temp variable in the sort function.

Type Item
	Field Index%	; integer for this example
End Type

For n = 1 To 15 : t.Item = New Item : t\Index = Rand(9) : Next ; test data

ShowData
InsertionSort
ShowData

WaitKey

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

Function InsertionSort()
Local Item.Item, NextItem.Item
Local p.Item, q.Item
Local temp%	; must be same type as the sort field.

	NextItem=After First Item
	While NextItem<>Null
		Item=NextItem
		NextItem=After Item
		p=Item : temp=Item\Index
		Repeat
			q=Before p
			If q=Null Then Exit
			If temp >= q\Index Then Exit
			p=q
		Forever
		q=Item
		Insert q Before p
	Wend
	
End Function

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

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

Comments

None.

Code Archives Forum