Skip to content

Instantly share code, notes, and snippets.

@Tofunmi1
Created July 31, 2022 20:22
Show Gist options
  • Save Tofunmi1/6db53e88d071b3c4a17d5d292a87dde1 to your computer and use it in GitHub Desktop.
Save Tofunmi1/6db53e88d071b3c4a17d5d292a87dde1 to your computer and use it in GitHub Desktop.
Bubble sort algorithm in yul

Recursive Implementation Of Bubble Sort in solidity and yul

***credit -> geekforgeeks -> https://www.geeksforgeeks.org/bubble-sort/

The idea is to place the largest element at their position and keep doing the same for every other elements.

Approach:

Place the largest element at their position, this operation makes sure that first largest element will be placed at the end of array. Recursively call for rest n – 1 elements with same operation and placing the next greater element at their position. Base condition for this recursion call would be, when number of elements in the array becomes 0 or 1 then, simply return (as they are already sorted).

// SPDX-License-Identifier: MIT
/// @author: Tofunmi
pragma solidity >=0.8.0;
library BubbleSort {
/// recursive bubble sort algorithm
// check readme for explanation
function bubbleSort(uint256[] memory _arr, uint256 n) internal pure {
//if n is zero or one, stop the sort
assembly {
switch n
case 0x00 {
return(0, 0)
}
case 0x01 {
return(0, 0)
}
for {
let i := 0
} lt(i, sub(n, 1)) {
i := add(i, 0x01)
} {
/// The array _arr has been storred in memory already
/// the first 32 byte of an array stored in memory is the length
/// So to get to the first value of the array we have to add 32 bytes to it.
/// Since we are in a lop, every iteration we need to add 32., e.g for the second add 64
/// So to get the current value we have 32 * i + 32 → 32 * (i + 1) → which in
/// assembly is mul(0x20, add(i, 1)) (simple brackets fractorisation)
let x := mload(add(_arr, mul(0x20, add(i, 1))))
/// to get arr[i - 1], add 32 bytes to y
let y := mload(add(add(_arr, mul(0x20, add(i, 1))), 0x20))
if gt(x, y) {
mstore(add(add(_arr, mul(0x20, add(i, 1))), 0x20), x)
mstore(add(_arr, mul(0x20, add(i, 1))), y)
}
}
}
/// recurse
bubbleSort(_arr, n - 1);
}
function normBubbleSort(uint256[] memory _arr, uint256 n) internal pure {
if (n == 0 || n == 1) {
return;
}
for (uint256 i = 0; i < n - 1; ) {
if (_arr[i] > _arr[i + 1]) {
(_arr[i], _arr[i + 1]) = (_arr[i + 1], _arr[i]);
}
unchecked {
++i;
}
}
normBubbleSort(_arr, n - 1);
}
}
//// SPDX-License-Identifier: MIT
pragma solidity >=0.8.13;
import "../bubblesort.sol";
import "../../lib/forge-std/src/Test.sol";
contract BubbleSortTest is Test {
function testBubbleSortAsmHardcoded() public {
unchecked {
uint256[] memory b = new uint256[](6);
b[0] = 1;
b[1] = 3;
b[2] = 2;
b[3] = 5;
b[4] = 6;
b[5] = 4;
BubbleSort.bubbleSort(b, 6);
emit log_array(b);
uint256[] memory bSorted = new uint256[](6);
bSorted[0] = 1;
bSorted[1] = 2;
bSorted[2] = 3;
bSorted[3] = 4;
bSorted[4] = 5;
bSorted[5] = 6;
assertEq(b, bSorted);
bytes memory _b = abi.encodePacked(b);
for (uint256 i = 1; i < b.length; ++i) {
assertTrue(b[i - 1] <= b[i]);
}
}
}
function testBubbleSortNormal() public {
unchecked {
uint256[] memory b = new uint256[](6);
b[0] = 1;
b[1] = 3;
b[2] = 2;
b[3] = 5;
b[4] = 6;
b[5] = 4;
BubbleSort.normBubbleSort(b, 6);
for (uint256 i = 1; i < b.length; ++i) {
assertTrue(b[i - 1] <= b[i]);
}
bytes memory _b = abi.encodePacked(b);
// console.logBytes(_b);
}
}
function testBubbleSortAssembly() public {
unchecked {
uint256[] memory b = new uint256[](6);
uint8[6] memory a = [1, 3, 2, 5, 6, 4];
b[0] = 1;
b[1] = 3;
b[2] = 2;
b[3] = 5;
b[4] = 6;
b[5] = 4;
BubbleSort.bubbleSort(b, 6);
for (uint256 i = 1; i < b.length; ++i) {
assertTrue(b[i - 1] <= b[i]);
}
bytes memory _b = abi.encodePacked(b);
// console.logBytes(_b);
}
}
function testBubbleSortRandom(uint256[] memory a) public {
unchecked {
vm.assume(a.length < 7);
BubbleSort.bubbleSort(a, 6);
for (uint256 i = 1; i < a.length; ++i) {
assertTrue(a[i - 1] <= a[i]);
}
bytes memory _b = abi.encodePacked(a);
// console.logBytes(_b);
}
}
function testSortChecksumed(uint256[] memory a) public {
unchecked {
vm.assume(a.length < 2048);
uint256 checksum;
for (uint256 i = 0; i < a.length; ++i) {
checksum += a[i];
}
BubbleSort.bubbleSort(a, a.length);
uint256 checksumAfterSort;
for (uint256 i = 0; i < a.length; ++i) {
checksumAfterSort += a[i];
}
assertEq(checksum, checksumAfterSort);
for (uint256 i = 1; i < a.length; ++i) {
assertTrue(a[i - 1] <= a[i]);
}
}
}
function testSortDifferential(uint256[] memory a) public {
unchecked {
vm.assume(a.length < 128);
// Make a copy of the `a` and perform insertion sort on it.
uint256[] memory aCopy = new uint256[](a.length);
for (uint256 i = 0; i < a.length; ++i) {
aCopy[i] = a[i];
}
for (uint256 i = 1; i < aCopy.length; ++i) {
uint256 key = aCopy[i];
uint256 j = i;
while (j != 0 && aCopy[j - 1] > key) {
aCopy[j] = aCopy[j - 1];
--j;
}
aCopy[j] = key;
}
BubbleSort.bubbleSort(a, a.length);
// Compare the results.
for (uint256 i = 0; i < a.length; ++i) {
assertEq(a[i], aCopy[i]);
}
}
}
function testSort(uint256[] memory a) public {
unchecked {
vm.assume(a.length < 2048);
BubbleSort.bubbleSort(a, a.length);
for (uint256 i = 1; i < a.length; ++i) {
assertTrue(a[i - 1] <= a[i]);
}
}
}
function testSortBasicCase() public {
unchecked {
uint256[] memory a = new uint256[](2);
a[0] = 3;
a[1] = 0;
BubbleSort.bubbleSort(a, a.length);
for (uint256 i = 1; i < a.length; ++i) {
assertTrue(a[i - 1] <= a[i]);
}
}
}
function testSortPsuedorandom() public {
unchecked {
uint256[] memory a = new uint256[](100);
uint256 lcg = 123456789;
for (uint256 i; i < a.length; ++i) {
a[i] = lcg;
lcg = (lcg * 1664525 + 1013904223) & 0xFFFFFFFF;
}
BubbleSort.bubbleSort(a, a.length);
for (uint256 i = 1; i < a.length; ++i) {
assertTrue(a[i - 1] <= a[i]);
}
}
}
function testSortSorted() public {
unchecked {
uint256[] memory a = new uint256[](100);
for (uint256 i; i < a.length; ++i) {
a[i] = i;
}
BubbleSort.bubbleSort(a, a.length);
for (uint256 i = 1; i < a.length; ++i) {
assertTrue(a[i - 1] <= a[i]);
}
}
}
function testSortReversed() public {
unchecked {
uint256[] memory a = new uint256[](100);
for (uint256 i; i < a.length; ++i) {
a[i] = 999 - i;
}
BubbleSort.bubbleSort(a, a.length);
for (uint256 i = 1; i < a.length; ++i) {
assertTrue(a[i - 1] <= a[i]);
}
}
}
}
Running 11 tests for src/test/bubbleSort.t..sol:BubbleSortTest
[PASS] testBubbleSortAssembly() (gas: 3775)
Traces:
[3775] BubbleSortTest::testBubbleSortAssembly()
└─ ← 0x000000000000000000000000000000000000000000000000000000000000000600000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000002
[PASS] testBubbleSortNormal() (gas: 9337)
Traces:
[9337] BubbleSortTest::testBubbleSortNormal()
└─ ← ()
[PASS] testBubbleSortNormalFreeStyle() (gas: 3635)
Traces:
[3635] BubbleSortTest::testBubbleSortNormalFreeStyle()
└─ ← 0x000000000000000000000000000000000000000000000000000000000000000600000000000000000000000000000000000000000000000000000000000000010000000000000000000000000000000000000000000000000000000000000002
[PASS] testBubbleSortRandom(uint256[]) (runs: 256, μ: 6962, ~: 6870)
[PASS] testSort(uint256[]) (runs: 256, μ: 1686230, ~: 1169578)
[PASS] testSortBasicCase() (gas: 840)
Traces:
[840] BubbleSortTest::testSortBasicCase()
└─ ← 0x000000000000000000000000000000000000000000000000000000000000000200000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000003
[PASS] testSortChecksumed(uint256[]) (runs: 256, μ: 1701789, ~: 1180147)
[PASS] testSortDifferential(uint256[]) (runs: 256, μ: 756744, ~: 614049)
[PASS] testSortPsuedorandom() (gas: 761720)
Traces:
[761720] BubbleSortTest::testSortPsuedorandom()
└─ ← 0x0000000000000000000000000000000000000000000000000000000000000064000000000000000000000000000000000000000000000000000000000011c1cb00000000000000000000000000000000000000000000000000000000024ca216
[PASS] testSortReversed() (gas: 886160)
Traces:
[886160] BubbleSortTest::testSortReversed()
└─ ← 0x000000000000000000000000000000000000000000000000000000000000006400000000000000000000000000000000000000000000000000000000000003840000000000000000000000000000000000000000000000000000000000000385
[PASS] testSortSorted() (gas: 623168)
Traces:
[623168] BubbleSortTest::testSortSorted()
└─ ← 0x000000000000000000000000000000000000000000000000000000000000006400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
Test result: ok. 11 passed; 0 failed; finished in 15.00s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment