Bubble Sorter

This is a bubblesorter design built in C++ for Vivado HLS.

Bubble Sorter

Bubble sorting is a relatively inefficient algorithm when compared to other techniques such as Quicksort, but is very simple to implement. It works by successively comparing adjacent elements in a list and swapping them if they are not in the correct order. It requires multiple iterations of the list before it is finally sorted. When the bubblesorter completes a scan of the list without executing any swaps, then the list is know to be sorted.

This version of the bubble sorter has a couple of optimizations:

• For each scan, the position of the last executed swap is noted - we can assume all elements in the list after the last swap position are already sorted. This means we can ignore them on the next scan, effectively the list to be scanned gets shorter with every scan.
• For each scan, a boolean flag (swapDone) indicates if a swap was done or not. If it is false after a scan then the list is sorted and the bubble sorter has finished.

The design has been simulated in the Vivado HLS environment and tested in hardware, the C testbench is included in the download on my git hub page. You will need a Vivado development system to compile the design, the WebPack version is free to download.

If you have any questions or comments about this design, please email me at designs@markharvey.info