Insertion Sort

Monkey Forums/Monkey Code/Insertion Sort

impixi

(Posted 2011) [#1]

Sort an integer array using the 'insertion sort' algorithm.

Strict

#rem
	INSERTION SORT
	(December 2011)
	
	PORTED FROM Javascript code located at:
	<a href="http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort" target="_blank">http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort</a>
#end


Function InsertionSort:Void(input:Int[])
	
	For Local i:Int = 1 Until input.Length
		Local value:Int = input[i]
		Local j:Int = i - 1
		While ((j >= 0) And (input[j] < value))
			input[j + 1] = input[j]
			j -= 1
		Wend
		input[j+1] = value
	Next

End


'------- EXAMPLE --------------------------------


Function Main:Int()
	
	Local arr:Int[] = [10, -4, 19, 100, -22, 17, 92, 10, 4, 66, 2, 0, -2, -10, 4, 5]
	
	Local str:String = "-----------------------~nUnsorted:~n"
	For Local i:Int = 0 Until arr.Length
		str += arr[i] + ", "
	Next
	
	'*************
	InsertionSort arr
	'*************
	
	str += "~n-----------------------~nSorted:~n"
	For Local i:Int = 0 Until arr.Length
		str += arr[i] + ", "
	Next
		
	str += "~n-----------------------~n"
		
	Print str	
	
	Return 0
	
End

impixi

(Posted 2011) [#2]

A class-embedded example:

Strict

#rem
	INSERTION SORT: CLASS-EMBEDDED EXAMPLE
	(December 2011)
#end


Function Main:Int()
	
	Local players:Player[] = New Player[5]
	
	For Local i:Int = 0 Until players.Length
		players[i] = New Player("Player " + (i+1), Floor(Rnd(0.0, 1000.0)))
	Next
	
	Local str:String = "-----------------------~nUnsorted:~n"
	For Local i:Int = 0 Until players.Length
		str += players[i].name + ": " + players[i].score + "~n"
	Next
	
	'*************
	Player.SortArray players, Player.GET_SCORE_HIGH
	'*************
	
	str += "-----------------------~nSorted (descending, on score):~n"
	For Local i:Int = 0 Until players.Length
		str += players[i].name + ": " + players[i].score + "~n"
	Next
		
	'*************
	Player.SortArray players, Player.GET_NAME_HIGH
	'*************
	
	str += "-----------------------~nSorted (descending, on name):~n"
	For Local i:Int = 0 Until players.Length
		str += players[i].name + ": " + players[i].score + "~n"
	Next
		
	str += "-----------------------~n"	
		
		
	Print str	
	
	Return 0
	
End


'****************************


Class Player


	Field name:String
	Field score:Int

	
	Method New(name:String, score:Int)
	
		Self.name = name
		Self.score = score
	
	End


	'VVV SORTING-RELATED VVV

	Const GET_NAME_HIGH:Int = 0
	Const GET_SCORE_HIGH:Int = 1
	Const GET_NAME_LOW:Int = 2
	Const GET_SCORE_LOW:Int = 3

	Function Compare:Player(p1:Player, p2:Player, get:Int)
	
		Select get
		
			Case GET_NAME_HIGH
				If (p1.name > p2.name) Then Return p1 Else Return p2			
			
			Case GET_SCORE_HIGH
				If (p1.score > p2.score) Then Return p1 Else Return p2
			
			Case GET_NAME_LOW
				If (p1.name < p2.name) Then Return p1 Else Return p2
			
			Case GET_SCORE_LOW
				If (p1.score < p2.score) Then Return p1 Else Return p2
				
		End

		Return Null
		
	End

	Function SortArray:Void(input:Player[], get:Int)

		#rem
		Insertion sort based on Javascript code located at:
		<a href="http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort" target="_blank">http://rosettacode.org/wiki/Sorting_algorithms/Insertion_sort</a>
		#end
	
		For Local i:Int = 1 Until input.Length
			Local p:Player = input[i]
			Local j:Int = i - 1
			While ((j >= 0) And (Player.Compare(input[j], p, get) = p))
				input[j + 1] = input[j]
				j -= 1
			Wend
			input[j+1] = p
		Next

	End


End