Ordenar una matriz de enteros con Ethereum

Se genera un "destino de salto no válido" cuando accede a una matriz fuera de los límites. ¿Intentaste depurarlo en mix ?

El siguiente código parece funcionar. Al usar la palabra clave storageen el tipo de argumento, puede pasar una referencia de almacenamiento (solo funciona para funciones y bibliotecas internas); de lo contrario, los datos de almacenamiento se copiarían en la memoria. Como optimización, podría considerar copiar la matriz de almacenamiento en la memoria, verificar si está ordenada, si no, ordenarla y copiarla nuevamente en el almacenamiento. Otro peligro potencial relacionado con la solidez del navegador: debe ingresar los argumentos de la matriz como [1,7,4,5].

Ah, y la mejor optimización es, por supuesto, ordenar la matriz fuera de la cadena y solo verificar en la cadena si está ordenada o no.

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

Editar (2020-10): problema de subdesbordamiento solucionado por @subhodi y actualizado a la última versión de Solidity.

Algoritmo Quicksort sin ninguna excepción de VM: consulte esta esencia https://gist.github.com/subhodi/b3b86cc13ad2636420963e692a4d896f

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

Cuando j=0 y j-- conducen a un valor entero grande almacenado en la memoria de j, esto se debe a que j es del tipo uint (entero sin signo) y 0-1=-1 (j--) que j no puede almacenar, por lo que el valor de j será (2^256)-1. En el siguiente ciclo, cuando EVM lee arr[j], lee el valor basura que conduce a una excepción.

La solución de Chriseth se ve bien y limpia, y funcionaría en una implementación que use entradas firmadas en lugar de entradas sin firmar. Sin embargo, necesitaría cambiar la línea.

j--;

a

if (j > 0)  j--; 

si desea evitar obtener un subdesbordamiento de enteros.

La respuesta anterior de Subhod es buena, pero por el bien de la variedad, aquí hay una versión que escribí que evita ints por completo y mantiene todo uints. He pateado un poco los neumáticos, pero deberías probar más antes de implementarlo. También, por supuesto, como señaló Nick Johnson en Twitter , el peor de los casos de clasificación rápida es lento (O (n ^ 2)), por lo que es posible que desee encontrar uno más rápido 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);
}

El problema con su código es que está pasando una in-memorymatriz a la invocación recursiva. La matriz se pasa por copia (diferentes instancias en cada invocación) en lugar de por referencia (la misma matriz).

La solución de @chriseth es correcta porque usa storagela que se pasa por referencia. Desafortunadamente, este enfoque es muy costoso, ya que exige modificar el almacenamiento por contrato, que es la operación EVM más costosa.

El mejor enfoque es usar quickSort para ordenar los datos en la memoria. Puede lograrlo eliminando la recurrencia del código y reemplazándolo con una pila explícita.

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

Si está interesado en gas consumptiondiferentes algoritmos de clasificación en solidez, puede echar un vistazo a este repositorio .

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