Sorting algorithms in Blueprints

It is common knowledge that blueprints do not include sorting functions. In my previous experiences, I have been able to create simple sorting functions easily. However, during my current project, I faced the challenge of sorting large data arrays and found that the sorting process was either very slow or unsuccessful. Since I wanted to avoid using C++ code or third-party development, I independently researched this issue.

After conducting some research, I have decided to share my findings in the hopes that it will be useful to others. I started by studying the theory behind sorting algorithms and discovered that most functions I had previously written or seen on forums were variations of two simple algorithms: Selection and Insertion. However, these algorithms were ineffective for large arrays in blueprints, as they would fail or take a very long time to execute, even when I increased the loop limit to 100,000,000.

To address this issue, I studied several basic algorithms and chose a few to implement with blueprints for testing purposes. Below, I have listed the implemented algorithms in order of increasing performance and included statistics and average time values to compare their effectiveness.

BUBBLE SORT

SELECTION SORT

INSERTION SORT

The first three algorithms are slow and unsuitable for working with large and medium arrays.

COMB SORT

SHELL SORT

Comb sort and Shell sort work much better and show good results even on large arrays.

I noticed one interesting thing - all of the above algorithms work twice as slowly in macros.

The following two algorithms are more complex and contain recursion.

QUICK SORT

INTROSORT

I didn’t use heapsort as it’s overkill for blueprints and replaced insertion sort with comb sort as the results were better.

I used a shuffle at the input to the Quicksort and intro sort functions to avoid efficiency degradation on partially sorted arrays.

Quicksort and Introsort are the fastest, but they are unusable in macros due to recursion.

STATISTICS

Please look at the comparative results of testing algorithms I collected while working on this study.

StatFloatsFunc

StatFloatsMacro

CONCLUSIONS

In my Quiet Runtime Editor, I needed to sort large arrays of indexed names, and I found that the sorting process was taking a long time. However, after implementing the algorithms I’ve shared above, I achieved a 30-40 times speed improvement. While any of these algorithms will work for sorting small arrays, I recommend using Shellsort for medium and large arrays due to its simplicity and efficiency.

The project that prompted me to do this research:

Also, I’ve created a study project that includes all of the algorithms and auxiliary functions mentioned. The project also includes functions for sorting arrays of strings alphabetically, both with and without Numerical string sorting. Feel free to download and use it!

SortingAlgorithms_5.0.zip (326.6 KB)

It would be great if you added other algorithms and published your statistics to expand this research.

33 Likes

Just came across this on Reddit. This is so ■■■■■■■ great! Why not doing a plugin of this with function written in c++ but exposed in BP (if that’s not yet the case)?

I should have clarified that C++ code is several orders of magnitude faster, and on very large arrays, this is the only option.

There is a free plugin library:

5 Likes

Compare strings:

SIMPLE

WITH NUMERIC

Shell sort strings:

1 Like

SORT ACTORS

To sort any objects, we need to compare them by some parameter. Let’s first try to sort the actors by name.

You can also choose any other criterion for comparison. If you need a function to sort objects according to various parameters, you can create many comparison functions and select them by passing some key, for example, Enum.

Example:

image

3 Likes

This is the greatest thing ever and don’t let anyone tell you otherwise

2 Likes

Improved Shellsort

In this study, I implemented Shell sort with a simple selection of gaps. The average running time of the algorithm depends on the lengths of the intervals - d, which will contain the sorted elements of the original array with a capacity of N at each step of the algorithm. There are several approaches to choosing these values, and I selected Marcin Ciura’s empirical sequence.

StatFloatsFuncCiur

3 Likes

StatFloatsFuncHeap

2 Likes

I found a small mistake in my implementation of the improved Shellsort. Fixed the function and statistics.