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.
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.
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!
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)?
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.
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.
