[Script Bits] Sorting object arrays by property value

[niston]

Sometimes the need may arise to sort an array of objects, depending on the value of a certain property of those objects.

 

Luckily for us, Computer Science came up with some algorithms to do this around the late 50's / early 60's of the last century. How lore-friendly of Computer Science!

 

I am going to share with you today my Papyrus in-place implementations of two sorting algorithms: Bubble Sort and Quicksort. Bubble Sort is a rather simple algorithm that relies on repeatedly swapping array elements until they are in the right order. Quicksort on the other hand is a "divide-and-conquer" algorithm that relies on building partitions from array elements and then swapping elements along the divider, or pivot, line.

 

In-Place means that the algorithms operate directly on the array that needs to be sorted, as opposed to creating a new array containing the sorted elements. In-Place versions are much preferred, because the alternative would be extremely problematic with Papyrus, as Papyrus can -for reasons that might have made sense around the turning of the last millennium- not add more than 128 elements to an array.

 

For the purpose of this demonstration, assume that we have an array myObjectArray of MyObject type objects. The array contains n of these objects and each of the object has a Float Property called ZLevel. Assume that we want to sort those objects, so the array will contain the object with the lowest ZLevel value at index 0 and the object with the highest ZLevel value at index n - 1.

 

So let's try first with Bubble Sort:

Function BubbleSort(MyObject[] myObjectArray)
	; Simple In-Place BubbleSort
	Int n = myObjectArray.Length
	Int i = 0
	While (i < (n - 1))
		Int j = 0
		While (j < (n - i - 1))
			If (myObjectArray[j].ZLevel > myObjectArray[j + 1].ZLevel)
				MyObject temp = myObjectArray[j]
				myObjectArray[j] = myObjectArray[j + 1]
				myObjectArray[j + 1] = temp
			EndIf
			j += 1
		EndWhile
		i += 1
	EndWhile
EndFunction

As you can see, the algorithm steps through the array repeatedly, comparing each object with the next one and swapping them, if applicable. While this algorithm is extremely simple to implement, it's going to be slow for large arrays, because it's average complexity is n^2 - the same as it's worst case complexity, which is O(n^2). This means that, on average, the algorithm needs to perform n^2 iterations to complete the sort, which will become a rather large number very quick for arrays with more than just a handful objects in it: It's going to be painfully or even prohibitively slow.

 

So what do we do if we need to sort more than just a small bunch of objects? We resort to another sorting algorithm, that's what we do.

 

Enter Quicksort:

Function QuickSort(MyObject[] myObjectArray, Int left = 0, Int right = 0)
	; Recursive In-Place QuickSort
	If (right == 0)
		right = (myObjectArray.Length - 1)
	EndIf
	If (left < right)
		Int pivot = QuickSortPartition(myObjectArray, left, right)
		
		If (pivot > 1)
			QuickSort(myObjectArray, left, pivot - 1)
		EndIf
		
		If (pivot + 1 < right)
			QuickSort(myObjectArray, pivot + 1, right)
		EndIf
	EndIf
EndFunction

Int Function QuickSortPartition(MyObject[] myObjectArray, Int left, Int right)
	Float pivot = myObjectArray[left].ZLevel
	Int i = 1
	; limit iterations to worst case n^2 (safety measure for in-game use)
	While (i <= (myObjectArray.Length * myObjectArray.Length))
		While (myObjectArray[left].ZLevel < pivot)
			left += 1
		EndWhile
		While (myObjectArray[right].ZLevel > pivot)
			right -= 1
		EndWhile
		If (left < right)
			MyObject temp = myObjectArray[right]
			doors[right] = myObjectArray[left]
			doors[left] = temp
		Else
			Return right
		EndIf
		i += 1
	EndWhile
EndFunction

Unlike it's simpler Bubble Sort cousin, the Quick Sort algorithm has an average complexity of just O(n log n), whereas the worst case complexity at O(n^2) is the same as for Bubble Sort. This means that QuickSort will, on average, be much faster than Bubble Sort, the speed advantage increasing with the number of objects in the array.

 

You will notice that QuickSort is a recursive algorithm (the QuickSort function calls itself), so it will have more processing overhead than the simple Bubble Sort. We can exploit this fact and use Bubble Sort for small arrays with a limited number of elements, while resorting to QuickSort if there is a larger number of elements in our array:

Function Sort(MyObject[] myObjectArray)
	If (myObjectArray.Length <= 5)
		; bubblesort is faster for small arrays (less overhead)
		BubbleSort(myObjectArray)
	Else
		; quicksort is faster for larger arrays (overhead is comparatively negligible)
		QuickSort(myObjectArray)
	EndIf
EndFunction

If you want to adapt these algorithms to your own objects, you will have to adjust tests of the ZLevel property to some property name that's actually on your objects. It must be a comparable value, meaning that < and > operators must be able to work with the datatype of the property.

 

 

Have fun sorting!

[SKKmods]

A handy reminder, but have you tested a worst case partition pick on a 128 element quick sort ?

 

Typically a script function will crash at 48/49 recursive calls with [ error: Stack too deep (infinite recursion likely) - aborting call and returning None ]

[niston]

This is interesting.

 

I've reached a recursion depth of 55 in my testing (sorting 61 elevator floors by ZLevel), without any crash or error.

 

Strange, because even in the best case with partition being perfectly balanced, complexity is O(n), so it seems that this should not work at all.

 

I shall make my elevator exceed 128 floors and report back.$

 

EDIT:

 

[03/04/2020 - 01:46:36PM] [crp:elevatorcontroller < (A505376A)>]: Recursion depth=94

[03/04/2020 - 01:46:36PM] error: Stack too deep (infinite recursion likely) - aborting call and returning None

On a side note: "Infinite recursion likely" at a depth of 94? Preposterous! Thanks SKK for pointing out this silly limitation.

So we will have to resort to a non-recursive implementation. Unfortunately we can't use a stack either, due to the other silly 128 array elements limit.

[SKKmods]

I ran a sequence of simple Function A calls Function B recursions and consistently get the issue at:

[03/04/2020 - 01:53:27PM] SKK_GlobalUtility.RecursionA count 48.000000
[03/04/2020 - 01:53:27PM] error: Stack too deep (infinite recursion likely) - aborting call and returning None

on both fully modded all DLC L99 savegame or a clean no DLC/mods vault exit.

 

Anyhoo it reminds me of first learning about bubble and quick sorts waaaaaay back in the days of 1Mhz CPUs ... even then multi dim arrays would support 256 x 32768 elements.

[niston]

1MHz CPU? 6502/6510 and Z80 come to mind :)

 

I wonder how many times Beth shot themselfes in the foot already, due to those arbitrary limits.

[SKKmods]

You got your history nailed ;)

 

Thank the (lord | lead architect) for an unlimited count RefCollectionAlias to avoid having to manage chained arrays of stuff.

[niston]

I'm using reflinks to work around the 128 array limit in this case.

 

But I still need to sort all reflinked doors by ZLevel.

 

On a side note though: Having an elevator with 132 floors in a test cell makes my game crash on loading a save. Funny enough, I can still coc to the testcell from the main menu.

EDIT: It was just that a restart was in order. *shrug*

[SKKmods]

If you can AddRef them in order a RefCollectionAlias it will maintain its element index so you can do Find and GetAt to figure where you are in the stack.

 

I have also used formlists and AddForm() with ObjectReferences for this but they do something odd like add new elements at [0] and shift everything up so you have to add in reverse. Memo: may not be 100% correct, its been a while.

[niston]

I will check it out, as I only found a single description of a Quicksort that doesnt require neither a stack nor uses recursion. And the paper costs 25 bucks to look at :)

[niston]

Here we go with an iterative QuickSort implementation that uses a "smaller partition first" strategy and will sort up to 2^128 objects by their ZLevel property value. In theory at least, because Papyrus is really really sloooooow and 2^128 is a really really extremely large number.

 

All credits go to Darel Rex Finley - I merely ported his C code to Papyrus and adapted it to work with MyObject.ZLevel:

Function QuickSortByZLevel(MyObject[] doors)
	; based on "Optimized QuickSort - C Implementation" by darel rex finley (http://alienryderflex.com/quicksort/)		
	Int MAX_LEVEL = 128 Const
	Int[] Beg = new Int[MAX_LEVEL]
	Int[] End = new Int[MAX_LEVEL]
	Int i = 0
	Int L
	Int R
	Int swap
	MyObject piv
	
	
	Beg[0] = 0
	End[0] = doors.Length
	
	While (i >= 0)
		L = Beg[i]
		R = End[i] - 1;
		If (L < R)
			piv = doors[L]
			While (L < R)
				While ((doors[R].ZLevel >= piv.ZLevel) && (L < R))
					R -= 1
				EndWhile
				If (L < R)					
					doors[L] = doors[R]					
					L += 1
				EndIf
				While ((doors[L].ZLevel <= piv.ZLevel) && (L < R))
					L += 1
				EndWhile
				If (L < R)					
					doors[R] = doors[L]
					R -= 1
				EndIf
			EndWhile
			doors[L] = piv
			Beg[i + 1] = L + 1
			End[i + 1] = End[i]			
			End[i] = L
			i += 1
			If (End[i] - Beg[i] > End[i - 1] - Beg[i - 1])
				swap = Beg[i]
				Beg[i] = Beg[i-1]
				Beg[i - 1] = swap
				swap = End[i]
				End[i] = End[i-1]
				End[i-1] = swap
			EndIf
		Else
			i -= 1		
		EndIf
	EndWhile
EndFunction

I built an elevator with 221 floors to verify. Much more isn't really practical, as its so slow.