Time for another weekly blog post. This week we will briefly talk about bubble sort. Bubble sort is a simple sorting algorithm that constantly compares the adjacent element and swaps it if it's not in order.
This is best used for arrays that are almost sorted due to their lengthy nature.
Below is an example of bubble sort.
let finished = false
while(!finished) {
finished = true
for(let i =1; i < array.length; i++){
if(array[i -1] > array[i]) {
finished = false
let temp = array[i -1]
array[i-1] = array[i]
array[i] = temp
}
}
}Below is a more in-depth example of it.
array = [[2,5,4,1,3]
first iteration: 3 swaps
[2,5,4,1,3]
[2,5,4,1,3]
— — — — — -
[2,5,4,1,3]
[2,4,5,1,3]
— — — — — -
[2,4,5,1,3]
[2,4,1,5,3]
— — — — — -
[2,4,1,5,3]
[2,4,1,3,5]
second iteration: 2 swaps
[2,4,1,3,5]
[2,4,1,3,5]
— — — — — -
[2,4,1,3,5]
[2,1,4,3,5]
— — — — — -
[2,1,4,3,5]
[2,1,3,4,5]
— — — — — -
[2,1,3,4,5]
[2,1,3,4,5]
third iteration: 1 swap
[2,1,3,4,5]
[1,2,3,4,5]
— — — — — -
[1,2,3,4,5]
[1,2,3,4,5]
— — — — — -
[1,2,3,4,5]
[1,2,3,4,5]
— — — — — -
[1,2,3,4,5]
[1,2,3,4,5]
fourth iteration: no swaps
[1,2,3,4,5]
[1,2,3,4,5]
— — — — — -
[1,2,3,4,5]
[1,2,3,4,5]
— — — — — -
[1,2,3,4,5]
[1,2,3,4,5]
— — — — — -
[1,2,3,4,5]
[1,2,3,4,5]
Bubble sort knows to stop sorting when it goes through the array and it does no swaps. Because of the amount it takes to complete it's best used when an array is almost sorted to avoid a lot of iterations. As you can see above it would need to complete 4 iterations but if the array only needed one swap then the total iterations needed to complete would be two. The first one for the swap. The second one to confirm everything is sorted. Hope this quick explanation is helpful to understand bubble sort.
