0

How is it possible in an ethereum contract to sort the public adresses of senders of eth in the contract in the alphanumeric order ?

bumped to the homepage by Community 2 days ago

This question has answers that may be good or bad; the system has marked it active so that they can be reviewed.

  • 1
    What is your question? – Ismael Nov 6 '18 at 4:34
  • I think you need to better explain what you try to do... – OWADVL Nov 6 '18 at 10:26
  • @NovaLova I think your question is too broad, it is more an exercise than a question about ethereum. – Ismael Nov 6 '18 at 15:21
  • It is maybe both (question and exercie) because it is about what is possible to do with ethereum – Nova Lova Nov 8 '18 at 9:28
0

Some observations:

  1. You'll only be able to make the allocations only after everybody submitted their weis. Otherwise, how will you know where to start the incrementation for address starting with 0x8F for example? If you re-do the allotments with each submission, the total gas cost will increase for each participant's entry.
  2. Sorting is quite a complex algorithm, which, if you do it in a smart contract, will make your method calls more expensive, the more participants you have. And I assume you'll most likely reach the block gas limit pretty fast (not to mention the prohibitive transactions costs up to that point). I'd suggest you to think of a business solution to make these sortings and the allotments of the bets outside the smart contract (in javascript or python) and then allocate the corresponding betting numbers to each address.

These being said, you actually can sort things in solidity. Have a look at this thread to see how.

In the above example, they're sorting the uint[] public data; array. You'll probably have an array like address[] public deponents; that you'll need to sort.

Given that ETH addresses are 20 byte values, one can apply sorting operators on them, so the sorting algo should work as is.

0

Yes, it is possible. You may compare addresses, and thus may sort them:

function sortAddresses (address [] memory addresses) public pure returns (address [] memory) {
    for (uint256 i = addresses.length - 1; i > 0; i--)
         for (uint256 j = 0; j < i; j++)
            if (addresses [i] < addresses [j])
                (addresses [i], addresses [j]) = (addresses [j], addresses [i]);

    return addresses;
}

Input:

0xC02aaA39b223FE8D0A0e5C4F27eAD9083C756Cc2
0x742d35Cc6634C0532925a3b844Bc454e4438f44e
0x4E9ce36E442e55EcD9025B9a6E0D88485d628A67
0x53d284357ec70cE289D6D64134DfAc8E511c8a3D
0x66f820a414680B5bcda5eECA5dea238543F42054
0xab7c74abC0C4d48d1bdad5DCB26153FC8780f83E
0x61EDCDf5bb737ADffE5043706e7C5bb1f1a56eEA
0xDc76CD25977E0a5Ae17155770273aD58648900D3

Output:

0x4E9ce36E442e55EcD9025B9a6E0D88485d628A67
0x53d284357ec70cE289D6D64134DfAc8E511c8a3D
0x61EDCDf5bb737ADffE5043706e7C5bb1f1a56eEA
0x66f820a414680B5bcda5eECA5dea238543F42054
0x742d35Cc6634C0532925a3b844Bc454e4438f44e
0xab7c74abC0C4d48d1bdad5DCB26153FC8780f83E
0xC02aaA39b223FE8D0A0e5C4F27eAD9083C756Cc2
0xDc76CD25977E0a5Ae17155770273aD58648900D3

Though, sorting large number of addresses at once could be bad idea because of gas limit concerns. Better approach would be to save addresses of senders into sorted tree, such as AVL tree. This way cumulative sorting cost will be higher, but it will be amortized among many transactions.

0

First all, why would you want to? It is seldom necessary to do something like that. A good rule of thumb is to treat sorting as a method of last resort.

In databases, sorted lists help efficiently locate keys of interest O(log n). In Ethereum contracts, mapping accomplishes the same in O(1). The most common reasons for sorting data are poor justifications for it in Ethereum contracts: https://blog.b9lab.com/the-joy-of-minimalism-in-smart-contract-design-2303010c8b09

There is more than one way to sort if you really need to. Linked lists and binary trees are candidates. The exact method to use depends on what you plan to do with the sorted data - what do you need to find? It also depends on the expected scale. It is vital that insertion, removal and retrieval can be guaranteed to execute below the gasLimit and below the maximum acceptable cost (for practical purposes) at the maximum possible set size. Otherwise, you will have a solution that doesn't scale.

A linked list is not especially good for finding and ranking random members but it can good for finding min/max or traversing the list in sorted order if that's all you want do. The gas cost can be kept under control by relying on clients to provide strong hints that reduce the search area: https://bitbucket.org/rhitchens2/soliditystoragepatterns/src/master/LinkedList.sol

You can use a binary tree with the caveat that this places an upper bound on the size of the set. https://github.com/rob-Hitchens/OrderStatisticsTree, https://github.com/bokkypoobah/BokkyPooBahsRedBlackTreeLibrary

In practice, it is usually more appropriate to rely on unsorted data inside a contract while strictly enforcing integrity rules (e.g. no duplicates). Clients are well-suited to sort the data at their leisure using their own resources as a matter of interpretation of the authoritative contract state.

Consider this:

  1. Given an authoritative list of all set members (in a contract).
  2. There is only one "correct" sorted list of the members. Clients are free to use any method they want to organize data observed in contracts. And, client-side processing is largely unconstrained by cost.
  3. Sorting and filtering are often merely presentation and reporting concerns.
  4. A client can present any sorted or filtered interpretation and it will alway be possible to confirm that the client was working (correctly) with data from the contract - nothing added, nothing overlooked.
  5. Unless the contract itself relies on sort order to perform on-chain logic there is probably no good reason to burden the contract with this concern.
  6. Many forms of integrity checking rely on existence checks which can be accomplished with appropriate data structures using mappings. https://github.com/rob-Hitchens/UnorderedKeySet

Hope it helps.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.