12

I'm trying to have a simple array of integer sorted in Solidity but i couldn't find any real ressources so instead i'm trying to do it "the hard way" but so far with very little success.

Is anyone aware of anything that could help ?

This is what i've tried so far , but with no luck. Whenever i try it i'm getting out of memory errors.

  function quickSort(uint[] arr, uint left, uint right) private returns(uint[] _arr){
      uint i = left;
      uint j = right;
      uint tmp;
      uint pivot = arr[(left + right) / 2];
      while (i <= j) {
            while (arr[i] < pivot)
                  i++;
            while (arr[j] > pivot)
                  j--;
            if (i <= j) {
                  tmp = arr[i];
                  arr[i] = arr[j];
                  arr[j] = tmp;
                  i++;
                  j--;
            }
      }
      if (left < j)
            quickSort(arr, left, j);
      if (i < right)
            quickSort(arr, i, right);
}

Anyone got something to share ?

Error is often " ERROR: invalid jump destination (PUSH1) "

Edit :

Same with :

function insertionSort(uint[] a){
 for (uint i = 1;i < a.length;i++){
  uint temp = a[i];
  uint j;
  for (j = i -1; j >= 0 && temp < a[j]; j--)
    a[j+1] = a[j];
  a[j + 1] = temp;
 }
}

edit 2 :

Fixed aswell

  function insertionSort(uint[] a)internal {
   for (uint i = 1;i < a.length;i++){
    uint temp = a[i];
    uint j;
    for (j = i -1; j >= 0 && temp < a[j]; j--)
      a[j+1] = a[j];
    a[j + 1] = temp;
   }
  }
11

"Invalid jump destination" is generated when you access an array out of bounds. Did you try debugging it in mix?

The following code seems to work. By using the keyword storage in the argument type you can pass a storage reference (only works for internal functions and libraries), otherwise the storage data would be copied to memory. As an optimization you might consider copying the storage array to memory, checking whether it is sorted, if not, sort it and copy it back to storage. Another potential pitfall concerning browser-solidity: You have to enter array arguments as [1,7,4,5].

Oh and the best optimization is of course to sort the array off-chain and only check on-chain whether it is sorted or not.

contract Sorter {

    uint[] public data;
    function set(uint[] _data) { data = _data; }
    function sort() {
        if (data.length == 0)
            return;
        quickSort(data, 0, data.length - 1);
    }

    function quickSort(uint[] storage arr, uint left, uint right) internal {
        uint i = left;
        uint j = right;
        uint pivot = arr[left + (right - left) / 2];
        while (i <= j) {
            while (arr[i] < pivot) i++;
            while (pivot < arr[j]) j--;
            if (i <= j) {
                (arr[i], arr[j]) = (arr[j], arr[i]);
                i++;
                j--;
            }
        }
        if (left < j)
            quickSort(arr, left, j);

        if (i < right)
            quickSort(arr, i, right);
    }
}
  • So there is no better way of sorting int arrays? – Joël Feb 20 '16 at 2:18
  • I've tried but as soon as i'm trying to create a transaction for the method which call the fonction i get Solidity exception(Bad Jump). I've tried with your web tool aswell and on my devchain but i'm kind of stuck. Are there restriction of access to array stored? – user697 Feb 20 '16 at 2:41
  • @user697 How much gas are you sending in your transaction? Start with 3,000,000 gas until things work, so that you avoid potential out of gas issues during development. – eth Feb 20 '16 at 5:25
  • Doesn't work. I don't think it's an issue with gas tho, i'm never out of gas. I think it's something i didn't understood about accessing array in memory. Any of you successfully reproduced ? I'm using a public array of 5 unsorted number as parameter. – user697 Feb 20 '16 at 15:32
  • 3
    Quicksort is O(log^2 n). with respect to size. Since size costs more than computation perhaps Heapsort would be better. The Wikipedia article notes that heapsort is used in small embedded systems, and you can consider the EVM a small embedded system. You should at least try it – Paul S Feb 22 '16 at 4:17
1

Quicksort algorithm without any VM exception: refer this gist https://gist.github.com/subhodi/b3b86cc13ad2636420963e692a4d896f

tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
i++;
j--; 

When j=0 and j-- leads to large integer value stored in j's memory this is because j is of type uint(unsigned integer) and 0-1=-1 (j--) which j cannot store so j's value will be (2^256)-1. In the next loop when EVM reads arr[j], it reads garbage value leading to exception.

1

Chriseth's solution looks good and clean and would work in an implementation using signed ints instead of unsigned ones. However you would need to change the line

j--;

to

if (j > 0)  j--; 

if you want to avoid getting an integer underflow.

0

The problem with your code is that you are passing an in-memory array to recursive invocation. The array is being passed by copy (different instances on every invocation) instead of by reference (the same array).

The solution from @chriseth is correct because it uses storage which is passed by reference. This approach if unfortunately very costly as it demands to modify contract storage which is the most expensive EVM operation.

The best approach is to use quickSort to sort data in memory. You may achieve by eliminating the recurrence from the code and replacing it with an explicit stack.

function sort(uint[] storage data) {

    uint n = data.length;
    uint[] memory arr = new uint[](n);
    uint i;

    for(i=0; i<n; i++) {
      arr[i] = data[i];
    }

    uint[] memory stack = new uint[](n+2);

    //Push initial lower and higher bound
    uint top = 1;
    stack[top] = 0;
    top = top + 1;
    stack[top] = n-1;

    //Keep popping from stack while is not empty
    while (top > 0) {

      uint h = stack[top];
      top = top - 1;
      uint l = stack[top];
      top = top - 1;

      i = l;
      uint x = arr[h];

      for(uint j=l; j<h; j++){
        if  (arr[j] <= x) {
          //Move smaller element
          (arr[i], arr[j]) = (arr[j],arr[i]);
          i = i + 1;
        }
      }
      (arr[i], arr[h]) = (arr[h],arr[i]);
      uint p = i;

      //Push left side to stack
      if (p > l + 1) {
        top = top + 1;
        stack[top] = l;
        top = top + 1;
        stack[top] = p - 1;
      }

      //Push right side to stack
      if (p+1 < h) {
        top = top + 1;
        stack[top] = p + 1;
        top = top + 1;
        stack[top] = h;
      }
    }

    for(i=0; i<n; i++) {
      data[i] = arr[i];
    }
  }

If you are interested in gas consumption by different sorting algorithms in solidity you may take a look at this repo.

  • Just tested your code and it consumes more gas then example with storage writes. For instance, only initial and final copying consumes ~1.2kk gas. – Alex G.P. May 7 '18 at 16:11
0
function sort_array(uint64[] arr_) returns (uint64 [] )
{
    uint256 l = arr_.length;
    uint64[] memory arr = new uint64[] (l);

    for(uint i=0;i<l;i++)
    {
        arr[i] = arr_[i];
    }

    for(i =0;i<l;i++)
    {
        for(uint j =i+1;j<l;j++)
        {
            if(arr[i]<arr[j])
            {
                uint64 temp= arr[j];
                arr[j]=arr[i];
                arr[i] = temp;

            }

        }
    }

    return arr;
}

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.