Ethereum – Sorting an Array of Integers in Ethereum Smart Contracts

contract-debuggingcontract-developmentgo-ethereumsolidity

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

Best Answer

"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.

// 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.

Related Topic