Bubble Sort
Algorithms #algorithms #sortingIterate over the array and push the largest element to the end (in case of ascending order)
- Average and worst case time complexity is O(n2), when array is already sorted in descending order
- O(n) is the best case when array is already sorted (and we stop after first swap)
fun main() {
val arr = intArrayOf(2, 1, 10, 0, 2)
println(arr.contentToString())
bubbleSort(arr)
println("sorted: ${arr.contentToString()}")
}
fun bubbleSort(arr: IntArray) {
for (i in 0 until arr.size.dec()) {
var swapped = false
for (j in 0 until arr.size.dec().minus(i)) {
if (arr[j] > arr[j.inc()]) {
val tmp = arr[j]
arr[j] = arr[j.inc()]
arr[j.inc()] = tmp
swapped = true
}
}
if (swapped.not()) {
break
}
}
}