DataStructure and Algorithm: Sorting : Bubble Sort

Bubble Sort

Bubble sort is a sorting algorithm that is implemented at beginning of the array and swapping the first two elements only if the first element is greater than the second element. This comparison is then moved onto the next pair and so on. This is done until the array is completely sorted.

E.g [9,4,10,3]

First Iteration

• Compare 9 with 4. 9 is greater than 4 then swipe 9 and 4 [4, 9, 10, 3]
• Compare 9 and 10. They are already in sorted order, so nothing will change [4, 9, 10, 3]
• Compare 10 with 3. 10 is greater than 3, then swipe 10 with 3. [4, 9, 3, 10]

Second Iteration

• Compare 4 with 9. It is already in sorted order, so nothing will change [4, 9, 3, 10]
• Compare 9 with 3. 9 is greater than 3 and swipe 9 with 3 [4, 3, 9, 10]
• Compare 9 with 10. It is already in sorted order, so nothing will change[4, 3, 9, 10]

Third Iteration

• Compare 4 with 3. 4 is greater than 3 then swipe 4 with 3 [ 3, 4, 9, 10]

Now the array is in sorted order.

Here time complexity of bubble sort is O(n) is array is already sorted, but in average and worst case it goes to O(n^2)

Bubble Sort

By the end of the first pass, the last element is guaranteed to be the largest.

Bubble sort example link:- https://github.com/nishant-kumbhare/SwiftDataStructureAndAlgorithm

Thank you for reading.