Godot Version
4.2.1
Question
The sorting algorithm in GDScript is not stable, which means it will shuffle the order of things that are considered to be equal.
For, for example, if I have an array of playing cards cards:
7 Spade, 8 Spade, 9 Spade, 3 Heart, 4 Spade
and I want to sort them by suit (with Spades first), then I can write a custom sorting algorithm that puts Spades before Hearts, but the end result might be:
9 Spade, 7 Spade, 4 Spade, 8 Spade, 3 Heart
If I want to sort by suit, the algorithm wont leave the order of things with the same suit alone, this is what’s called an “unstable” sort.
Having a stable sort is highly desirable and I’ve never encountered a programming language that didn’t have a built-in stable sort.
How should I solve this problem? Should I implement my own sorting algorithm in slow GDScript (slow compared to the underlying compiled C++ that is), or what?
Also, are there any plans to improve this aspect of GDScript, any tickets I can look at to track the progress or contribute?
Why not using array custom_sort?
You can use a callback to define the weight. Like, first the suit, then the number.
1 Like
You’ll have to implement your own stable sort. Start with bubble sort in GDScript, profile your typical sample size, change algorithm or drop down to C++ if really needed.
Array.sort() and Array.custom_sort() use heap sort which is an unstable sorting algorithm. This means that it may not keep elements with the same key in the same order between sorts. This includes sub-keys that can be implemented in custom sort.
1 Like
Okok! I didnt get he wants to keep the order despite the card number. My bad.
Insertion sort is quite simple also and a bit faster. Just to add some options. But if the maze inst big bubble sort is going to be easier to implement.
Sorry for the mistake 
1 Like
As mentioned, sort_custom is not a solution.
To complete my example, if I want to sort the following so that Spades come before Hearts:
7S, 8S, 9S, 3H, 4S (S = Spade, H = Heart)
A stable sort would result in:
7S, 8S, 9S, 4S, 3H
Notice that it maintains the order of the items as much as possible.
What custom sorting function could I write that would give that output?
There is no generally applicable custom sort function that would maintain the existing order of items like this.
The best solution is to make the built-in array sorting algorithm stable. This can be done in a backwards compatible way because (1) stable sorting algorithms can be just as fast as unstable sorting algorithms and (2) the existing sorting algorithm has undefined behavior for equal items, and going from undefined behavior to defined behavior can be done in a backwards compatible way.
1 Like
I know this is totally out the main subject, but have you thought about just a different way of storing?
Like a specific array for each type. Example:
Your hand
S[ 7S, 8S, 9S ], H[3H]… Stash[.]
You get a cart so you push it into the stash array:
S[ 7S, 8S, 9S ], H[3H]… Stash[4S]
Then for ordering you just push it at the back of spade array in this case,
S[ 7S, 8S, 9S, 4S ], H[3H]… Stash[.]
As I said, just a different approach in case it may be interesting for your case. And maybe more effortless than adapting a sort algorigth.
I came across the same problem and came up with this:
func merge_sort(cards: Array) -> Array:
if cards.size() <= 1:
return cards
var mid = cards.size() / 2
var left = merge_sort(cards.slice(0, mid))
var right = merge_sort(cards.slice(mid, cards.size()))
return merge(left, right)
func merge(left: Array, right: Array) -> Array:
var result = []
var i = 0
var j = 0
while i < left.size() and j < right.size():
if left[i].value < right[j].value:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
while i < left.size():
result.append(left[i])
i += 1
while j < right.size():
result.append(right[j])
j += 1
return result
It will sort the card based on it’s card.value. To use it, just write something like this:
var cards = […you cards]
cards = merge_sort(cards)
I really hope they’ll fixed the sorting algorithm but it is still not stable in 4.3 rc1