Bubble Sort

Bubble Sort

• Bubble sort is an algorithm that compares the adjacent elements and swaps their positions if they are not in the intended order. 
• A list with n elements requires n-1 passes for sorting
• The order can be ascending or descending.
• It is known as bubble sort, because with every complete iteration the largest element in the given array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the water surface.

Algorithm: Following are the steps involved in bubble sort(for sorting a given array in ascending order):

1. Starting with the first element(index = 0), compare the current element with the next element of the array.
2. If the current element is greater than the next element of the array, swap them.
3. If the current element is less than the next element, move to the next element. Repeat Step 1.

How it works:
Bubble sort starts with very first two elements, comparing them to check which one is greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

The new array should look like this −

Next we compare 33 and 35. We find that both are in already sorted positions.

Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted.

We swap these values. We find that we have reached the end of the array. After one iteration (pass), the array should look like this − (This is what the list looks like after the first pass.)

To be precise, we are now showing how an array should look like after each iteration. After the second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.

And when there's no swap required, bubble sorts learns that an array is completely sorted.

Advantages:

• Easy to understand.

• Easy to implement.

• In-place, no external memory is needed.

• Performs greatly when the array is almost sorted.

Disadvantages

• Very expensive, O(n2)in worst case and average case.

• The main disadvantage of the bubble sort is the fact that it does not deal well with a list containing a huge number of items.

 

Share This:

Facebook

Twitter

Google Plus

Pinterest

Linkedin