mojira.dev
MC-268417

Entities are sorted with Bogosort when using [sort=nearest] and [sort=furthest]

I appreciate that you can sort entities by distance but why does Minecraft use the Bogosort algorithm? This algorithm is very inefficient unless you are lucky. To reproduce just run a command with [sort=nearest] or [sort=furthest]. The time how long it takes to sort will be random.

Related issues

Comments

[Mod] turbo

Is that a bug or feedback?

migrated

A bug

Rob23

Minecraft does not use the Bogosort algorithm, as seen here:

net.minecraft.commands.arguments.selector.EntitySelectorParser

public static final BiConsumer<Vec3, List<? extends Entity>> ORDER_NEAREST = (pos, entities) -> entities.sort((a, b) -> Doubles.compare(a.distanceToSqr(pos), b.distanceToSqr(pos)));
public static final BiConsumer<Vec3, List<? extends Entity>> ORDER_FURTHEST = (pos, entities) -> entities.sort((a, b) -> Doubles.compare(b.distanceToSqr(pos), a.distanceToSqr(pos)));
public static final BiConsumer<Vec3, List<? extends Entity>> ORDER_RANDOM = (pos, entities) -> Collections.shuffle(entities);

Minecraft does in fact use the default Java sorting algorithm provided by List.sort(...).

Quote directly taken from the documentation of List.sort:
"This implementation is a stable, adaptive, iterative mergesort that requires far fewer than n lg(n) comparisons when the input array is partially sorted, while offering the performance of a traditional mergesort when the input array is randomly ordered."
https://docs.oracle.com/en/java/javase/17/docs/api/java.base/java/util/List.html#sort(java.util.Comparator)

The simplest way to confirm that Minecraft does in fact not use Bogosort is to try to sort bigger amounts of entities. If Minecraft would use the Bogosort algorithm, sorting 100 entities should take approximately 10^151^ longer than sorting 10 entities. However, 100 entities can in fact be sorted by Minecraft in very few time.

The only concern is that, when specifying a selector @e[limit=...,sort=nearest], Minecraft will sort all of the entities before applying the limit. This causes the sorting process to be much slower than necessary. For example an @e[limit=1,sort=nearest] selector will run in O(n log(n)) where n is the total amount of entities, where it could run in O(n) time, going through every entity once. This could be solved by using bubblesort if the limit is low in comparison to the amount of entities. The interesting fact about bubblesort is, that after k iterations, the last k elements will be correctly sorted. Therefore, you could apply k=limit iterations of bubblesort on the n entities, resulting in a time complexity of O(nk). This can be beneficial if the amount of entities is in the thousands and we only want 2 or 3 entities.

Conclusion: Minecraft doesn't use Bogosort, however the sorting process might be accelerated by using bubblesort if the amount of entities sorted is much higher than the wanted limit (e.g. 1000 compared to 3).

migrated

(Unassigned)

Unconfirmed

(Unassigned)

1.20.4, 24w06a

Retrieved