Bubble Sort as extension to Swift-Arrays

Question

Task description:

Implement an extension for Array, which sorts the elements using the Bubble Sort-algorithm.

My implementation:

extension Array where Element: Comparable {
 mutating func bubbleSort() -> Array {
 var i = 0
 var j = 0
 
 while i < self.count - 1 {
 while j < self.count - 1 - i {
 if self[j] > self[j + 1] {
 self.swapAt(j, j + 1)
 }
 j += 1
 }
 j = 0
 i += 1
 }
 
 return self
 }
}
// Provided test-samples
var iArray = [12, 5, 4, 9, 3, 2, 1]
print(iArray.bubbleSort())
var iArray2 = ["f", "a", "b"]
print(iArray2.bubbleSort())
var iArray3 = [String]()
print(iArray3.bubbleSort())

It works fine with the provided samples, so I consider it correct (formally).

But are there any flaws within my solution? Can it be improved?

Would you have done it totally different? Why and how?

• greybeard: What description/specification of Bubble Sort have you started from? (I consider both the code presented as well as the one on Rosetta Code, well, unconventional.)
• michael.zech: @greybeard To be honest: I just checked some pseudo code and example implementations in other languages, until I got the idea. Then wrote my Swift one.
• ielyamani: Mark it as @inlinable and public. Add some documentation.
• ielyamani: You could make it even faster for large arrays by implementing the parallel version of bubble sort. On my local machine with 10 cores, it's at least ten times faster for large arrays (Starting from around 512 elements, I noticed the difference). Depending on the length of the input array, we could switch between normal and parallel BS using the Strategy Pattern.

Answer 1

One natural modification I'd consider an improvement is the use of for for the inner loop.

I think it more direct to let the outer control variable (i above) decrease rather than having it increase and subtract it from the number of items.

---

I find the Bubble Sort variant using a flag to remember whether there was any swap in the current outer iteration inconsequent - if you want to improve over just decreasing the limit for the inner loop (for loop, again), keep the highest index among swaps and use as the limit next time around.

• Martin R: Actually both loops (inner and outer) can be for loops.
• greybeard: (@MartinR: I tried to address that using (for loop, again). I don't suggest a for loop for the outer one because I prefer setting the new limit to the position of the last swap.)

Answer 2

The existing sort functions in the Swift standard library come in two flavors:

• A mutating method sort() which sorts a collection in-place and does not return a value, and
• a non-mutating method sorted() which leaves the given collection unchanged and returns a new collection with the sorted elements.

Your bubbleSort() method does both: It returns a sorted array and modifies the given argument. That may be unexpected to the user.

I would suggest to provide a mutating and a non-mutating variant like the standard sorting functions:

extension Array where Element: Comparable {
 mutating func bubbleSort() {
 // Sort the elements of `self` ...
 }
 
 func bubbleSorted() -> Array {
 var copy = self
 copy.bubbleSort()
 return copy
 }
}

Usage:

// Non-mutating sort:
let array1 = [12, 5, 4, 9, 3, 2, 1]
print(array1.bubbleSorted())
// Mutating sort:
var array2 = [12, 5, 4, 9, 3, 2, 1]
array2.bubbleSort()
print(array2)

Answer 3

To expand on greybeard’s observation (+1), consider an array that is already largely in order:

var iArray1 = [2, 1, 3, 4, 5, 9, 12]
iArray1.bubbleSort()
print(iArray1)

Your implementation will require 21 iterations. That is inefficient.

Refer to Bubble sort - Optimizing bubble sort:

The bubble sort algorithm can be optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n − 1 items when running for the n-th time:

procedure bubbleSort(A : list of sortable items)
 n := length(A)
 repeat
 swapped := false
 for i := 1 to n - 1 inclusive do
 if A[i - 1] > A[i] then
 swap(A[i - 1], A[i])
 swapped := true
 end if
 end for
 n := n - 1
 until not swapped
end procedure

More generally, it can happen that more than one element is placed in their final position on a single pass. In particular, after every pass, all elements after the last swap are sorted, and do not need to be checked again. This allows us to skip over many elements, resulting in about a worst case 50% improvement in comparison count (though no improvement in swap counts), and adds very little complexity because the new code subsumes the "swapped" variable:

To accomplish this in pseudocode, the following can be written:

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 := new
 until n ≤ 1
end procedure

E.g., in Swift, perhaps:

extension Array where Element: Comparable {
 mutating func bubbleSort() {
 var n = count
 while n > 1 {
 var newN = 0
 for i in 1 ..< n {
 if self[i-1] > self[i] {
 swapAt(i-1, i)
 newN = i
 }
 }
 n = newN
 }
 }
}

In this iArray1 example (which was already largely in order), rather than 21 iterations, this rendition will require only 6. Often, in large, completely random data sets, the improvement is more modest, but this illustrates the optimization opportunity.

(Needless to say, as Martin R said, +1, you should either sort-in-place or return a sorted result, but not both.)