728x90 AdSpace

Latest Article

How to use Bubble Sort sorting technique with Example ?


Probably the simplest and the most straight forward sorting technique that exists is bubble sort; simplest in the terms that it is very easy to understand and implement.
The process of bubble sort can be described as:
        i.            Make n-1 passes through the array.
  1. In each pass, compare each element arr[i] with arr[i+1] and swap the two if arr[i] > arr[i+1]
Now we’ll consider an example and apply the algorithm to study its meechanism. Let us consider that following is the array that is to be sorted:
Pass 0
99  23   6  72  67  15  24
Pass 1
23   6  72  67  15  24  99
Pass 2
 6  23  67  15  24  72  99
Pass 3
 6  23  15  24  67  72  99
Pass 4
 6  15  23  24  67  72  99
Pass 5
 6  15  23  24  67  72  99
Pass 6
 6  15  23  24  67  72  99
Looking at the passes, we make some important observations. In the first pass, the largest integer is placed in the proper position. In second and third passes, second and third largest integrs are positioned properly and so on. Therefore it is guaranteed that n-1 passes are sufficient to sort the array completely.

Improvements in Bubble Sort:

Now let us look for some improvements that can be introduced in the algortihm. First is based on the fact that after ith pass, elements in position n-i and greater are already sorted; so we dont need to compare them in the (i+1)th pass. Thus the number of comparisons will be reduced with each pass.
If we carefully look at the example we discussed, we see that the array was completely sorted after pass 4. The last two passes were then just a waste of time, making the process less effecient. So we need to check wether or not a swap has taken place during a pass. If no swap has taken place, it means that the array has been sorted and no further passes are required. This change can improve the effeciency of bubble sort sufficiently for sorted or almost sorted data.
Even after these improvements, bubble sort is not a very good choice especially when the file to be sorted is a large one. The only advantage bubble sort provides is that it is very simple to implement.
no image
  • Title : How to use Bubble Sort sorting technique with Example ?
  • Posted by :
  • Date : 07:01
  • Labels :

  • Blogger Comments
  • Facebook Comments


Post a Comment