Bubble sort algorithm in yul

README.md

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).

bubbleSort.sol

// 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);
    }
 
}

bubbleSort.t.sol

//// 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]);
            }
        }
    }
}

gistfile1.txt

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