Bubble sort is a very popular and a basic technique to sort an array elements. This technique is hardly used anywhere due to its high computational complexity. But here the concept of Bubble sort is demonstrated. In this technique, adjacent elements are sorted in every run. This way after some runs the array is sorted. There two type of architectures are possible for bubble sort one is parallel and another is serial. The parallel Bubble sort architecture for four data elements are shown below. The structure of BN block is shown in the post for bitonic sort.
If the bubble sort algorithm is implemented as parallel block it will consume more number of BN blocks for higher value of n. Thus for parallel implementation bubble sort is not suitable.
An alternative is to make the sorting architecture serial. by recursively applying the sorting technique. In this case the basic sub block is shown below in Figure 2.
This sub block is used to make the bubble sort algorithm serial. Output of this block is again fed to the input side. This way after some iterations bubble soring algorithm sorts a string of 8 elements. This technique is obviously time consuming. As it takes six clock periods to sort 8 elements. A start signal chooses the initial inputs and then the out put of the Sub block is selected by the MUXes.
