Complete Computer Knowledge Portal

Wednesday, June 19, 2013

Bubble Sort

It is the simplest type of sorting technique. In this sorting technique, first two elements are compared and if first element is greater than second, they are swapped. This process is repeated for each pair of adjacent elements to the end of the data set. It again starts with first two elements and repeat the process until no swap occurs.
This sorting technique can only be used for sorting small lists. This technique can also be used for the large lists if only few elements require sorting.

Important: Average and worst case performance of this sorting technique is O (n2).

Example: Consider the following unordered list 


5              10           3              1              9              0

First Pass

 5 <10 so there is no need of swapping.

5              10           3              1              9              0

10>3 hence swap them 

5              10           1              3              9              0

3<9 hence no need of swapping

0<9 hence swap them

5              10           1              3              0              9

Second Pass

5<10 hence no swapping required

10>1 hence swap them

5              1              10           3              0              9

Now 10> 3 hence, swap them

5              1              3              10           0              9

10>0, swap them

5              1              3              0              10           9

10>9 swap them

5              1              3              0              9              10

Third Pass

5>1 swap them

1              5              3              0              9              10

5>3 swap them

1              3              5              0              9              10

5 >0 swap them

1              3              0              5              9              10

0<9 hence no swapping required

9<10 hence no swapping required

Fourth Pass

1<3 hence no swapping required

3>0, swap them

1              0              3              5              9              10

3<5 no swapping required

5<9 no swapping requires

9<10 no swapping required

Fifth Pass

1>0  hence swap them

0              1              3              5              9              10

1<3 no swapping required

3<5 no swapping required

5<9 no swapping required

9<10 no swapping required

Sixth Pass

0              1              3              5              9              10

0<1 no swapping required

1<3 no swapping required

3<5 no swapping required

5<9 no swapping required

9<10 no swapping required

In the Sixth pass no swapping is required, hence list is sorted now.

No comments:

Post a Comment