Sortieren eines Integer-Arrays mit Ethereum

"Ungültiges Sprungziel" wird generiert, wenn Sie auf ein Array außerhalb der Grenzen zugreifen. Hast du versucht, es in Mix zu debuggen ?

Der folgende Code scheint zu funktionieren. Durch die Verwendung des Schlüsselworts storageim Argumenttyp können Sie eine Speicherreferenz übergeben (funktioniert nur für interne Funktionen und Bibliotheken), da sonst die Speicherdaten in den Speicher kopiert würden. Als Optimierung könnten Sie in Betracht ziehen, das Speicher-Array in den Speicher zu kopieren und zu prüfen, ob es sortiert ist. Wenn nicht, sortieren Sie es und kopieren Sie es zurück in den Speicher. Ein weiterer potenzieller Fallstrick in Bezug auf die Browser-Solidität: Sie müssen Array-Argumente als [1,7,4,5].

Oh, und die beste Optimierung besteht natürlich darin, das Array Off-Chain zu sortieren und nur On-Chain zu prüfen, ob es sortiert ist oder nicht.

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

Bearbeiten (2020-10): Unterlaufproblem von @subhodi behoben und auf die neueste Solidity-Version aktualisiert.

Quicksort-Algorithmus ohne VM-Ausnahme: Siehe diesen Kern https://gist.github.com/subhodi/b3b86cc13ad2636420963e692a4d896f

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

Wenn j = 0 und j-- zu einem großen ganzzahligen Wert führt, der im Speicher von j gespeichert ist, liegt dies daran, dass j vom Typ uint (Ganzzahl ohne Vorzeichen) und 0-1 = -1 (j--) ist, die j nicht speichern kann, also wird der Wert von j sein (2^256)-1. In der nächsten Schleife, wenn EVM arr[j] liest, liest es den Garbage-Wert, der zu einer Ausnahme führt.

Die Lösung von Chriseth sieht gut und sauber aus und würde in einer Implementierung funktionieren, die signierte Ints anstelle von unsignierten verwendet. Allerdings müssten Sie die Zeile ändern

j--;

zu

if (j > 0)  j--; 

wenn Sie einen ganzzahligen Unterlauf vermeiden möchten.

Die obige Antwort von Subhod ist gut, aber der Abwechslung halber habe ich hier eine Version geschrieben, die ints vollständig vermeidet und alles uints beibehält. Ich habe die Reifen ein bisschen getreten, aber Sie sollten weiter testen, bevor Sie es einsetzen. Wie Nick Johnson auf Twitter feststellte , ist der schlimmste Fall von Quicksort natürlich auch langsam (O(n^2)), sodass Sie vielleicht einen schnelleren O(n log n) finden möchten.

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

Das Problem mit Ihrem Code besteht darin, dass Sie ein in-memoryArray an den rekursiven Aufruf übergeben. Das Array wird per Kopie (verschiedene Instanzen bei jedem Aufruf) statt per Referenz (dasselbe Array) übergeben.

Die Lösung von @chriseth ist korrekt, da sie das verwendet storage, was als Referenz übergeben wird. Dieser Ansatz ist leider sehr kostspielig, da er die Änderung des Vertragsspeichers erfordert, der der teuerste EVM-Vorgang ist.

Der beste Ansatz ist die Verwendung von quickSort zum Sortieren von Daten im Speicher. Sie können dies erreichen, indem Sie die Wiederholung aus dem Code entfernen und durch einen expliziten Stapel ersetzen.

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

Wenn Sie an gas consumptionverschiedenen Sortieralgorithmen in Solidität interessiert sind, können Sie sich dieses Repo ansehen .

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