Skip to content

Instantly share code, notes, and snippets.

@subhodi
Created December 14, 2017 08:31
Show Gist options
  • Save subhodi/b3b86cc13ad2636420963e692a4d896f to your computer and use it in GitHub Desktop.
Save subhodi/b3b86cc13ad2636420963e692a4d896f to your computer and use it in GitHub Desktop.
Quick sort in Solidity for Ethereum network
pragma solidity ^0.4.18;
contract QuickSort {
function sort(uint[] data) public constant returns(uint[]) {
quickSort(data, int(0), int(data.length - 1));
return data;
}
function quickSort(uint[] memory arr, int left, int right) internal{
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);
}
}
@subhodi
Copy link
Author

subhodi commented May 29, 2018

@Ipseeta there are some efficient sorting algorithms but i doubt Solidity implementations of such.

@sdelvalle57
Copy link

@0xAshish
Copy link

@sdelvalle57 seriously bubble sort O(n*n) over quick sort O(nlogn) ?
merge sort, i can still consider.

@huyhoangk50
Copy link

@0xAshish merge sort uses a lot of extra memory. Will that cost a lot of gas.

@ebulku
Copy link

ebulku commented Nov 3, 2020

Is there any descending implementation of quicksort in solidity?

@ASAPSegfault
Copy link

@0xAshish @huyhoangk50
The authors of this paper studied gas price and runtime of quick sort, merge sort and bubble sort algorithms on a Ganache private blockchain. Their results tells us that, among those, quick sort algorithm is best fitted to Ethereum.

Of course, this is not the main net, and a lot of things depends on their configuration of Ganache's chain and of their implementation of sorting algorithms themselves, but the information is, in my opinion, still useful to get an overview.

You may also want to check this thread.

@0xSumitBanik
Copy link

@ebulku , Sort the Array and Reverse it.

@ebulku
Copy link

ebulku commented Apr 4, 2022

@ebulku , Sort the Array and Reverse it.

I commented this years ago, and there is a simple one during quicksort: https://stackoverflow.com/questions/64661313/descending-quicksort-in-solidity

@EightRice
Copy link

what do left and right mean in that context?

@0xSumitBanik
Copy link

what do left and right mean in that context?

The left and right pointers pointing to the array elements.

@gsscoder
Copy link

gsscoder commented Feb 3, 2023

@0nova
Copy link

0nova commented Mar 6, 2024

This can help possibly

contract QuickSort {
    function quickSort(uint[] memory arr) public pure returns (uint[] memory) {
        if (arr.length <= 1) {
            return arr;
        }

        quickSortImpl(arr, 0, int(arr.length - 1));
        return arr;
    }

    function quickSortImpl(uint[] memory arr, int left, int right) private pure {
        if (left < right) {
            int pivotIndex = partition(arr, left, right);

            if (pivotIndex > 1) {
                quickSortImpl(arr, left, pivotIndex - 1);
            }

            if (pivotIndex + 1 < right) {
                quickSortImpl(arr, pivotIndex + 1, right);
            }
        }
    }

    function partition(uint[] memory arr, int left, int right) private pure returns (int) {
        uint pivot = arr[uint(right)];
        int i = left - 1;

        for (int j = left; j < right; j++) {
            if (arr[uint(j)] <= pivot) {
                i++;
                (arr[uint(i)], arr[uint(j)]) = (arr[uint(j)], arr[uint(i)]);
            }
        }

        (arr[uint(i + 1)], arr[uint(right)]) = (arr[uint(right)], arr[uint(i + 1)]);
        return i + 1;
    }

}

@0nova
Copy link

0nova commented Mar 6, 2024

This takes 350K gas with 100 elements

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment