Sorting an Array of integer with Ethereum

Question

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;
   }
  }

Answer 1

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

The following code seems to work, but the best optimization is of course to sort the array off-chain and only check on-chain whether it is sorted or not.

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

function quickSort(uint[] memory arr, int left, int right) 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)]);
            i++;
            j--;
        }
    }
    if (left < j)
        quickSort(arr, left, j);
    if (i < right)
        quickSort(arr, i, right);
}

contract QuickSort {
    function sort(uint[] memory data) public pure returns (uint[] memory) {
        quickSort(data, int(0), int(data.length - 1));
        return data;
    }
}

Edit (2020-10)

Underflow problem fixed by @subhodi and updated to latest Solidity version.

Answer 2

Subhod's answer above is good, but for variety's sake, here's a version I wrote that avoids ints entirely and keeps everything uints. I've kicked the tires a bit but you should test further before deploying it. Also of course, as Nick Johnson noted on Twitter, quicksort's worst case is slow (O(n^2)) so you might want to find a faster O(n log n) one.

function sort(uint[] memory arr) public pure {
    if (arr.length > 0)
        quickSort(arr, 0, arr.length - 1);
}

function quickSort(uint[] memory arr, uint left, uint right) public pure {
    if (left >= right)
        return;
    uint p = arr[(left + right) / 2];   // p = the pivot element
    uint i = left;
    uint j = right;
    while (i < j) {
        while (arr[i] < p) ++i;
        while (arr[j] > p) --j;         // arr[j] > p means p still to the left, so j > 0
        if (arr[i] > arr[j])
            (arr[i], arr[j]) = (arr[j], arr[i]);
        else
            ++i;
    }

    // Note --j was only done when a[j] > p.  So we know: a[j] == p, a[<j] <= p, a[>j] > p
    if (j > left)
        quickSort(arr, left, j - 1);    // j > left, so j > 0
    quickSort(arr, j + 1, right);
}

Answer 3

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.

Answer 4

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.

Answer 5

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.

Answer 6

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;
}