How to Implement Bubble Sort Algorithm in Swift and Java

Bubble sort is a sorting algorithm which can sort the lists in O(n²) 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(n²). 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 i^th iteration, you will have first i^th elements sorted.

Bubble sort works by moving bigger elements out with each iteration and sorting them. It bubble out the bigger elements and have i^th 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 i^th iteration as they are already sorted or skipping the elements after last swap position as they should be already in sorted order.

Swift Implementation

We calculate the length of the input and store it at the start.  After that 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:

https://gist.github.com/SanjeevMohindra/24063b1469de738961d313bb2092edd0

Java Implementation

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.

https://gist.github.com/SanjeevMohindra/18330fd95b3a537fd0db8c097fab1784

These are the implementation for Bubble Sort in Swift and Java. You can use the comment section regarding any questions on Bubble Sort.