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

@Ipseeta Ipseeta commented Jan 24, 2018

Is there any efficient way to sort apart from quicksort?

@subhodi

This comment has been minimized.

Copy link
Owner Author

@subhodi subhodi 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

@0xAshish 0xAshish 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

@huyhoangk50 huyhoangk50 commented Nov 22, 2018

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

@ebulku

This comment has been minimized.

Copy link

@ebulku ebulku commented Nov 3, 2020

Is there any descending implementation of quicksort in solidity?

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