How to sort an array of Struct by multiple keys in Solidity?

Question

I have such a struct

struct OfferBid {
            string id_user;
            uint qty_energy;
            uint typ;
            uint price_energy;
            uint status;
            uint t_submission;
            uint ts_delivery;
            uint number;
            uint quality_energy;
       }

and I have an array of this struct:

OfferBid[] tempOffers;

I found out how to sort tempOffers by price_energy. I use this function which creates an array of unit from the field price:

function quickSortOffersBidsPrice(Lb.Lib.OfferBid[] memory arr, bool ascending) public view returns(Lb.Lib.OfferBid[] memory) {
        if(arr.length == 0) return arr;
        uint[] memory prices = lib.arr_of_prices_offerbids(arr);
        Lb.Lib.OfferBid[] memory sorted = get_indices_and_sort(prices,arr,ascending);
        return sorted;
    }

which calls these other functions: Here I create an array of unit with the indices of the array of struct.

function get_indices_and_sort(uint[] memory values, Lb.Lib.OfferBid[] memory offers_bids, bool ascending) private pure returns(Lb.Lib.OfferBid[] memory) {
        uint[] memory indices = new uint[](values.length);
        for (uint z = 0; z < indices.length; z++) {
            indices[z] = z;
        }
        Sorting.quickSort_indices(values, 0, int(values.length-1), indices);
        if(!ascending){
            indices = reverseArray(indices);
        }
        Lb.Lib.OfferBid[] memory sorted = new Lb.Lib.OfferBid[](values.length);
        for (uint z = 0; z < indices.length; z++) {
            sorted[z] = offers_bids[indices[z]];
        }
        return sorted;
    }

I sort the array of prices and then at the same time the indices. Then I can sort the original array of struct

function quickSort_indices(uint[] memory arr, int left, int right, uint[] memory indices) public pure {
        int i = left;
        int j = right;
        if (i == j) return;

        uint pivot = arr[uint(left + (right - left) / 2)];

        while (i <= j) {
            while (arr[uint(i)] < pivot) i++;
            while (pivot < arr[uint(j)]) j--;
            if (i <= j) {
                (arr[uint(i)], arr[uint(j)]) = (arr[uint(j)], arr[uint(i)]);
                (indices[uint(i)], indices[uint(j)]) = (indices[uint(j)], indices[uint(i)]);
                i++;
                j--;
            }
        }
        if (left < j)
            quickSort_indices(arr, left, j, indices);
        if (i < right)
            quickSort_indices(arr, i, right, indices);
    }

How can I sort it first by price_energy, and in case of same price_energy, sort it byqty_energy?

Mad Jackal · Accepted Answer · 2020-12-26 20:50:01Z

0

Since int256 has a sufficiently large dimension, you can use the composite key for ordering: key= (price_energy<<128) | qty_energy

In addition, it may be more efficient to order the array not after its complete formation, but incrementally - as elements are added.

answered Dec 26, 2020 at 20:50

Mad Jackal

1,2491 gold badge8 silver badges11 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

haravares · Accepted Answer · 2022-06-27 18:39:40Z

0

According to this answer. Сustomize a next sample:

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract Sort {
    uint public total = 5;
    mapping(uint => Item) private itemIdToItem;
    struct Item { 
        uint id;
        uint price;
    }

    constructor() {
        itemIdToItem[1] = Item(1, 2);
        itemIdToItem[2] = Item(2, 5);
        itemIdToItem[3] = Item(3, 1);
        itemIdToItem[4] = Item(4, 3);
        itemIdToItem[5] = Item(5, 4);
    }

    /**
     * @dev Returns tuple(uint256,uint256)[]: 1,2, 2,5, 3,1, 4,3, 5,4 
     */
    function getItems() public view returns(Item[] memory) {
        uint totalMatches = 0;
        Item[] memory matches = new Item[](total);

        for (uint i = 1; i <= total; i++) {
            Item memory e = itemIdToItem[i];
            matches[totalMatches] = e;
            totalMatches++;
        }
        return matches;
    }

    /**
     * @dev Returns tuple(uint256,uint256)[]: 3,1, 1,2, 4,3, 5,4, 2,5
     */
    function sortByPrice() public view returns(Item[] memory) {
        Item[] memory items = getItems();

        for (uint i = 1; i < items.length; i++)
            for (uint j = 0; j < i; j++)
                if (items[i].price < items[j].price) {
                    Item memory x = items[i];
                    items[i] = items[j];
                    items[j] = x;
                }

        return items;
    }
}

edited Jun 27, 2022 at 18:39

answered Jun 27, 2022 at 18:13

haravares

5521 gold badge6 silver badges13 bronze badges

1 Comment

Extrange planet Over a year ago

If the array has 10000000 of records... out of gas in 3,2,1....

GDeep · Accepted Answer · 2022-10-22 19:53:01Z

0

This function should be enough to sort the array of objects/structs that contain price values. To include the other keys, we can compare them in if condition before swiping the values.

function sortByPrice() public view returns(PrintableResources[] memory) {
    PrintableResources[] memory items = printableResources;

    for (uint i = 1; i < items.length; i++)
        for (uint j = 0; j < i; j++)
            if (items[i].price < items[j].price) {
                PrintableResources memory x = items[i];
                items[i] = items[j];
                items[j] = x;
            }

    return items;
}

answered Oct 22, 2022 at 19:53

GDeep

497 bronze badges

Collectives™ on Stack Overflow

How to sort an array of Struct by multiple keys in Solidity?

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related