The best way to sort values

Solidity Programming
#1

Hello excellent Moralis community.
I come to you as always as a consultation for your kind willingness to help.
Thank you in advance.

The question is what would be the most appropriate and cheapest way in relation to gas to order some values associated with some accounts.

For example, we have a mapping of key address and value of positions 1, 2, 3.
And another mapping with the same address but this time associated with scores, e.g. 100, 633, 321.

What I am looking for is to order the first mapping in relation to the values of the second one.

It occurs to me to do it with an array instead of with a second mapping. But the handling of arrays is very expensive and I imagine that there will be another way to do it cheaper.

Any idea?

#2

I have searched for sorting algorithms and I have taken this one which I think is an insertion sort algorithm. But when I execute the sort function I get an undefined error. I don’t think that the function remains without gas so I don’t know what can be the error.

uint []  data = [12, 34, 2, 132, 5];

        function sort() public  {
            uint length = data.length;
            for (uint i = 1; i < length; i++) {
                uint key = data[i];
                uint j = i - 1;
                while ((int(j) >= 0) && (data[j] > key)) {
                    data[j + 1] = data[j];
                    j--;
                }
                data[j + 1] = key;
            }
        }

        function getData() public view returns(uint [] memory) {
            return data;
        }
#3

The solution was to cast the unsigned variables. This algorithm now seems to work in pragma solidity 8.

 function sort() public  {
            uint length = data.length;
            for (uint i = 1; i < length; i++) {
                uint key = data[i];
                int j = int(i) - 1;
                while ((int(j) >= 0) && (data[uint(j)] > key)) {
                    data[uint(j + 1)] = data[uint(j)];
                    j--;
                }
                data[uint(j + 1)] = key;
            }
        }
2 Likes
#4

Just to clarify, insertion sort is not the best way to sort values. It can be sufficient for your use case which should be fine. If we are using array, standard algorithm would be merge sort which has O(n log n) worst time complexity where as insertion sort average time complexity is O(n ^ 2). Another option would be to use Quick Sort. It can be useful if we need in-place sorting with O(1) space complexity, though its worst time complexity can be O(n ^ 2). But these two work way better than insertion sort. And people generally use them. Explanation & sample implementation link:
https://www.w3spot.com/2021/03/working-merge-sort-implementation-in.html
https://www.w3spot.com/2021/03/quicksort-implementation-in-java.html

#5

thank you very much for the important clarification