Bubble Sorting

Explanation of bubble Sorting

Naive Version

Image that a fish at the bottom of water tank blows bubbles, the bubbles will rise in the tank until they reach the water surface. That is similar to how bubble sorting algorithm works.

To start with, assuming we have this set of numbers and we want to sort it in inscending order:

The original set of number: 3,3,6,5,2,1,7

The result set of number: 1,2,3,3,5,6,7

Then we compare each two number next to each other from left to right, if the one on the left is larger than the right one, swap them:

If we continue to do it n(the length of set) times, the set is sorted in order.

Improvement

After 1 large round, we can see that we have the largest number at the most right place. If we keep doing swaps, at n round, we will have the n_st largest number set on its final position.

In this case, each large round we only need to compare the first n-m(the large round number) numbers instead of all n numbers.

Pros and Cons of bubble sorting

Pros

1. The space complexity is low.
2. The algorithm is stable which means that the positions of two equal numbers won’t change after the sorting. This property is quite useful when sorting complex structured data.

   Cons

3. The time complexity is high which is O(n²).

   Implementation

   Python

def bubbleSort(list):
    for i in range(0,len(list)-1):
        for j in range(0,len(list)-i-1):
            if list[j] > list[j+1]:
                temp = list[j]
                list[j] = list[j+1]
                list[j+1] = temp
    return list

print(bubbleSort([3,3,6,5,2,1,7]) )

Java

class Bubble{
    int[] list;
    public Bubble(int[] list){
        this.list = list;
    } 
    public int[] sort(){
        for (int i =0;i<this.list.length-1;i++){
            for (int j=0;j<this.list.length-1-i;j++){
                if(list[j]>list[j+1]){
                    int temp = list[j];
                    list[j] = list[j+1];
                    list[j+1] = temp;
                }
            }
        }
        return list;
    }
}
public class BubbleSort{
    public static void main(String[] args) { 
        int[] list = {3,3,6,5,2,1,7};
        Bubble bubble = new Bubble(list);
        int [] ans = bubble.sort();
        for(int num:ans){
            System.out.println(num);
        }
    }
}