Bubble Sort is the simplest sorting algorithm which iterates over elements of the array and swap adjacent elements if they are in wrong order. It repeat iterations until all elements will be in right order.
Example of unsorted and sorted array
let array = [19, 2, 66, 4, 45, 99, 101, 3, 5, 7, 17, 35, 42]
let sortedArray = [2, 3, 4, 5, 7, 17, 19, 35, 42, 45, 66, 99, 101]
First Version
We just iterate over elements and compare adjacent. And swap them in case of wrong order.
Also we use special variable counter for counting number of operations.
func bubbleSort1(array: [Int]) -> [Int] {
var result = array
let n = result.count
var counter = 0
for _ in 0..<(n - 1) {
for j in 0..<(n - 1) {
counter += 1
if result[j] > result[j + 1] {
let temp = result[j]
result[j] = result[j + 1]
result[j + 1] = temp
}
}
}
print("Count of operations in bubbleSort1: \(counter)")
return result
}
Check the result of the algorithm. Time complexity of this algorithm is O(nˆ2) because of two for loops.
let result1 = bubbleSort1(array: array)
// Count of operations in bubbleSort1: 144
assert(result1 == sortedArray, "Error happened!")
Second Version
We can improve first solution. Because after each iteration over the array the biggest element moving to the end of the array. So, after first iteration we can compare only before n-2, after second iteration only before n-3 and etc. So we can change upper limit for inner for loop.
func bubbleSort2(array: [Int]) -> [Int] {
var result = array
let n = result.count
var counter = 0
for i in 0..<(n - 1) {
for j in 0..<(n - i - 1) {
counter += 1
if result[j] > result[j + 1] {
result.swapAt(j, j + 1)
}
}
}
print("Count of operations in bubbleSort2: \(counter)")
return result
}
After optimisation we can see that number of operation is decreased, now it takes 78 instead of 144 in first solution. But still time complexity of algorithm is O(nˆ2) because there are two for loops.
let result2 = bubbleSort2(array: array)
// Count of operations in bubbleSort2: 78
assert(result2 == sortedArray, "Error happened!")
Third Version
We can optimise our solution even more. If after next iteration there were no swapping operations happened it means that array is sorted and we can exit from for loop. It gives us linear time complexity O(n) in case of array is already sorted, because we will have only one loop over n-elements for comparing elements.
func bubbleSort3(array: [Int]) -> [Int] {
var result = array
let n = result.count
var counter = 0
var isSwapped: Bool
for i in 0..<(n - 1) {
isSwapped = false
for j in 0..<(n - i - 1) {
counter += 1
if result[j] > result[j + 1] {
result.swapAt(j, j + 1)
isSwapped = true
}
}
if !isSwapped {
break
}
}
print("Count of operations in bubbleSort3: \(counter)")
return result
}
We can see that count of operation is slightly decreased, now it is 63 instead of 78.
let result3 = bubbleSort3(array: array)
// Count of operations in bubbleSort3: 63
assert(result3 == sortedArray, "Error happened!")
But count of operations will be decreased significantly for case when array is sorted: from 63 to 12
print("Comparing, unsored array: \(bubbleSort3(array: array))")
// Count of operations in bubbleSort3: 63
print("Comparing, sorted array: \(bubbleSort3(array: sortedArray))")
// Count of operations in bubbleSort3: 12
Fourth Version
The same optimised algorithm but written with using while loop.
func bubbleSort4(array: [Int]) -> [Int] {
var result = array
var counter = 0
let n = result.count
var lastUnsorted = n - 1
var isSorted = false
while (!isSorted) {
isSorted = true
for i in 0..<(lastUnsorted) {
counter += 1
if result[i] > result[i + 1] {
result.swapAt(i, i + 1)
isSorted = false
}
}
lastUnsorted -= 1
}
print("Count of operations in bubbleSort4: \(counter)")
return result
}
Result of work
let result4 = bubbleSort4(array: array)
// Count of operations in bubbleSort3: 63
assert(result4 == sortedArray, "Error happened!")
Making Generic Function
We can make generic function and use this algorithm for arrays with any type. Main condition that elements of the array are confirmed to Comparable protocol. Now we can sort array of strings, for example.
// Comparable:
// A type that can be compared using the relational operators <, <=, >=, and >.
func genericBubbleSort<T: Comparable>(list: [T]) -> [T] {
var result = list
let n = result.count
var lastUnsorted = n - 1
var isSorted = false
while (!isSorted) {
isSorted = true
for i in 0..<lastUnsorted {
if result[i] > result[i + 1] {
result.swapAt(i, i + 1)
isSorted = false
}
}
lastUnsorted -= 1
}
return result
}
let stringsArray = ["China", "Japan", "Brazil", "Russia", "Ireland"]
genericBubbleSort(list: stringsArray)
// ["Brazil", "China", "Ireland", "Japan", "Russia"]
Making Extension
We can also make extension for more handy usage of our algorithm.
extension Array where Element: Comparable {
func bubbleSort() -> [Element] {
var result = self
let n = result.count
var lastUnsorted = n - 1
var isSorted = false
while (!isSorted) {
isSorted = true
for i in 0..<lastUnsorted {
if result[i] > result[i + 1] {
result.swapAt(i, i + 1)
isSorted = false
}
}
lastUnsorted -= 1
}
return result
}
}
[19, 2, 66, 4, 45, 99, 101, 3, 5, 7, 17, 35, 42].bubbleSort()
// [2, 3, 4, 5, 7, 17, 19, 35, 42, 45, 66, 99, 101]
["China", "Japan", "Brazil", "Russia", "Ireland"].bubbleSort()
// ["Brazil", "China", "Ireland", "Japan", "Russia"]
Source Code
Source code for this post could be found here on
GitHub
