Сортировка массива целых чисел с помощью Ethereum

«Недопустимый пункт назначения перехода» генерируется при доступе к массиву за пределами границ. Вы пытались отлаживать его в миксе ?

Следующий код работает. Используя ключевое слово storageв типе аргумента, вы можете передать ссылку на хранилище (работает только для внутренних функций и библиотек), иначе данные хранилища будут скопированы в память. В качестве оптимизации вы можете рассмотреть возможность копирования массива хранения в память, проверки того, отсортирован ли он, если нет, отсортируйте его и скопируйте обратно в хранилище. Еще одна потенциальная ловушка, связанная с надежностью браузера: вы должны вводить аргументы массива как [1,7,4,5].

Да, и лучшая оптимизация, конечно, состоит в том, чтобы сортировать массив вне цепочки и только проверять в цепочке, отсортирован он или нет.

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

Редактировать (2020-10): проблема недостаточного заполнения исправлена ​​@subhodi и обновлена ​​​​до последней версии Solidity.

Алгоритм быстрой сортировки без каких-либо исключений VM: см. этот обзор https://gist.github.com/subhodi/b3b86cc13ad2636420963e692a4d896f

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

Когда j=0 и j-- приводит к большому целочисленному значению, хранящемуся в памяти j, это происходит потому, что j имеет тип uint(целое число без знака) и 0-1=-1 (j--), которые j не может хранить, поэтому значение j будет (2^256)-1. В следующем цикле, когда EVM читает arr[j], он считывает мусорное значение, приводящее к исключению.

Решение Chriseth выглядит хорошо и чисто и будет работать в реализации, использующей знаковые целые числа вместо беззнаковых. Однако вам нужно будет изменить строку

j--;

к

if (j > 0)  j--; 

если вы хотите избежать целочисленного потери значимости.

Ответ Subhod выше хорош, но для разнообразия я написал версию, которая intполностью избегает s и сохраняет все uints. Я немного пинал шины, но вам следует провести дополнительные испытания, прежде чем развертывать их. Также, конечно, как заметил Ник Джонсон в Твиттере , в худшем случае быстрая сортировка медленная (O(n^2)), поэтому вы можете найти более быструю O(n log n).

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

Проблема с вашим кодом заключается в том, что вы передаете in-memoryмассив рекурсивному вызову. Массив передается копией (разные экземпляры при каждом вызове) вместо ссылки (тот же массив).

Решение от @chriseth правильное, поскольку оно использует storageпереданное по ссылке. Этот подход, к сожалению, очень дорогостоящий, так как требует изменения контрактного хранилища, которое является самой дорогой операцией EVM.

Лучший подход — использовать quickSort для сортировки данных в памяти. Вы можете добиться этого, убрав повторение из кода и заменив его явным стеком.

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

Если вас интересуют gas consumptionразличные алгоритмы сортировки по плотности, вы можете взглянуть на этот репозиторий .

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