solidityでquicksort(使いやすい)
https://ethfiddle.com/_cKcOFL8HU
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 |
pragma solidity ^0.4.18; contract SimpleStore { uint[] private a = new uint[](10); function getA() public view returns(uint[]) { return a; } function setLen(uint _len) public { require(_len < 32); a.length = _len; } function _getRandomHash() private view returns (bytes32) { return keccak256(now); } function _bytes32ToUintArray(bytes32 b) private pure returns(uint[32] memory ret){ for(uint i=0; i<32; i++){ ret[i] = uint(b[i]); } } function init() public { uint[32] memory b = _bytes32ToUintArray(_getRandomHash()); for(uint i=0; i<a.length; i++){ a[i] = b[i]; } } function _calcCloneArray(uint[] _a) private pure returns(uint[]) { uint aLen = _a.length; uint[] memory b = new uint[](aLen); for(uint i=0; i<aLen; i++){ b[i] = _a[i]; } return b; } function doQuicksort() public { uint[] memory b = _calcCloneArray(a); _quicksort(b); a = b; } function _quicksort(uint[] _a) private pure { uint left = 0; uint right = _a.length - 1; _quicksort_core(_a, left, right); } function _quicksort_core(uint[] _a, uint _left, uint _right) private pure { if(_right <= _left){ return; } uint l = _left; uint r = _right; uint p = _getPivot(_a[l], _a[l+1], _a[r]); while(true){ while(_a[l] < p){ l++; } while(p < _a[r]){ r--; } if(r <= l){ break; } _swap(_a, l, r); l++; r--; } _quicksort_core(_a, _left, l - 1); _quicksort_core(_a, r + 1, _right); } function _getPivot(uint _a, uint _b, uint _c) private pure returns(uint) { if(_a < _b){ if(_b < _c){ return _b; }else{ return _a < _c ? _a : _c; } }else{ if(_a < _c){ return _a; }else{ return _b < _c ? _b : _c; } } } function _swap(uint[] _a, uint _l, uint _r) private pure { uint t = _a[_l]; _a[_l] = _a[_r]; _a[_r] = t; } } |
