Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
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);
}
}
@Ipseeta

This comment has been minimized.

Copy link

commented Jan 24, 2018

Is there any efficient way to sort apart from quicksort?

@subhodi

This comment has been minimized.

Copy link
Owner Author

commented May 29, 2018

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

@sdelvalle57

This comment has been minimized.

@0xAshish

This comment has been minimized.

Copy link

commented Sep 19, 2018

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

@huyhoangk50

This comment has been minimized.

Copy link

commented Nov 22, 2018

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.