Skip to content

Instantly share code, notes, and snippets.

@noidexe
Last active May 24, 2024 00:13
Show Gist options
  • Save noidexe/035066470a441e50bff624f895ec0360 to your computer and use it in GitHub Desktop.
Save noidexe/035066470a441e50bff624f895ec0360 to your computer and use it in GitHub Desktop.
Stable Sort by Property Value
# Implements a stable sort as requested in https://www.reddit.com/r/godot/comments/1cyyaxo/are_there_any_plans_to_implement_a_stable_sorting/
# in the worst possible way
extends Node
class TestObject extends RefCounted:
const SUITES = ['♠️','♣️','♥️','♦️']
var an_int : int
var a_float : float
var a_string : String
func _init() -> void:
an_int = randi_range(0, 100)
a_float = randf()
a_string = SUITES.pick_random()
func _to_string() -> String:
return "(%s, %s, %s)" % [an_int, a_float, a_string]
func _ready() -> void:
_test(10, "an_int", true)
_test(10, "a_float", true)
_test(10, "a_string", true)
_test(100, "an_int")
_test(10_000, "an_int")
_test(100_000, "an_int")
_test(1_000_000, "an_int")
_test(100, "a_float")
_test(10_000, "a_float")
_test(100_000, "a_float")
_test(1_000_000, "a_float")
_test(100, "a_string")
_test(10_000, "a_string")
_test(100_000, "a_string")
_test(1_000_000, "a_string")
func _test(amount : int, comparison_prop : StringName, print_result := false):
var array = []
for i in amount:
array.append(TestObject.new())
var start_time = Time.get_ticks_msec()
var sorted = sort_objects_by_prop(array, comparison_prop)
print("Prop name: %s. Amount: %s Elapsed: %sms" % [comparison_prop, amount, (Time.get_ticks_msec() - start_time)] )
if print_result:
print(array)
print(sorted)
static func sort_objects_by_prop( array : Array, comparison_prop : StringName) -> Array:
var split = {}
# split the array in groups based on the value of comparison_prop
for object: Object in array:
var prop_value = object.get(comparison_prop)
if split.has(prop_value):
split[prop_value].append(object)
else:
split[prop_value] = [object]
var prop_values = split.keys()
# Find the order the groups should have
prop_values.sort()
var ret = []
# Merge the groups in order
for p in prop_values:
ret.append_array(split[p])
return ret
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment