Bubble sort is a sorting algorithm which can sort the lists in O(n2) time.
Last time we talked about Insertion Sort implementation in Swift and Java, we have seen that insertion sort also does the same work in O(n2). So whats the difference between Insertion sort and Bubble Sort?
The major difference between bubble sort and insertion sort is that, insertions sort tries to sort the list element-by-element. After each ith iteration, you will have first ith elements sorted.
Bubble sort works by moving bigger elements out with each iteration and sorting them. It bubble out the bigger elements and have ith element sorted out at the end of the list.
Insertion sort uses less number of swaps than Bubble sort and mostly result in better run time. If the list is already in sorted condition, Insertion sort works better than Bubble Sort.
Bubble Sort Algorithm
Here is a pseudo-code for the algorithm (Source Wikipedia):
procedure bubbleSort( A : list of sortable items ) n = length(A) repeat newn = 0 for i = 1 to n-1 inclusive do if A[i-1] > A[i] then swap(A[i-1], A[i]) newn = i end if end for n = newn until n = 0 end procedure
The idea is to compare the elements next to each other and swap them in case first one is bigger than the second one. This way each iteration will bubble the largest element to the last of the list.
We can do some more optimization like, skipping last i element in ith iteration as they are already sorted or skipping the elements after last swap position as they should be already in sorted order.
We calculate the length of the input and store it at the start. We will loop till the input length is greater then zero.
We will create a pointer called forwardPointer, which will keep an location pointer for each iteration. Compare each element with its previous element (as we are starting with offset 1) and swap in case previous element is bigger.
Also set the newn (last known position of swap) to the position of swap. This is the position after which complete list is sorted. So we will reset the input length to newn, as that the remaining array needs to be sorted.
Once it’s done, you will have sorted list. Lets take a look at the implementation in Swift:
Here is the Java implementation of the Bubble sort. The logic is similar to what we have used in Swift implementation, you can check the walk-through of the same for details.
These are the implementation for Bubble Sort in Swift and Java. You can use the comment section regarding any questions on Bubble Sort.