In Bubble Sort method to sort array of n element first we create (n-1) bubble (Collection of two successive array element).
In first pass first element of each bubble is compared with second element of bubble such that , If first element is greater than second element of bubble both are swapped.
After performing such (n-1) comparison and swaps largest element of array move to last position of array i..e its sorted location. After performing such (n-1) passes we get a sorted array.
ALGORITHM OF BUBBLE SORT:
ALGORITHM Bubble Sort (A, N)
A IS AN ARRAY WITH N ELEMENT.
STEP 1 : FOR I=1 TO N-1 DO
STEP 2 : FLAG = 0
STEP 3 : FOR J =1 TO N-1 DO
STEP 4 : IF A[ J - 1 ] > A[ J ]
STEP 4.1: TEMP = A[ J - 1 ]
STEP 4.2: A[ J -1 ] = A [ J ]
STEP 4.3: A[ J ] = TEMP
STEP 4.4: FLAG = 1
STEP 5 : END IF
STEP 6 : NEXT J
STEP 7 : IF FLAG == 0 THEN GOTO J
STEP 8 : NEXT I
STEP 9 : END
FUNCTION OR PROCEDURE IN C:
Void bubblesort ( int a[50] , int n)
{
int i, j, flag, temp;
for ( i=1 ; i <= n-1 ; i++)
{
flag = 0;
for ( j= 1; j<= n-i ; j++)
{
if (a[ j-1 ] > a[ j ])
{
temp = a[j -1];
a[ j-1] = a[ j ];
a[ j ] = temp;
Flag = 1;
}
}
if ( Flag == 0)
break;
}
}
EXAMPLE:
EXPLANATION :
By the help of above figure we can easily understand the working of Bubble Sort. In above example we take 5 number of element for sorting , so n=5 . These five elements are { 17 , 19 , 3 , 4 , 13 }, these elements are stored in any array a[50] = { 17 , 19 , 3 , 4 , 13 }, a[index] index = 0,1,2,3,4 it represent the position of elements in array. Here all elements are sorted in IV Passes ( I ) represent number of passes. The outer loop is controlled by I and the inner loop is controlled by J. On the basis of I & J values elements are compared. Such as a[0] i.e 17 ,a[1] i.e 19 etc.
Comparison Method : For one outer loop i.e value of I, inner loop will run [<=( n-I )] times. The mechanism of inner loop is controlled by J and terminated by value of I. Here the main mechanism is swapping between number with condition [ if (a[ J-1 ] > a[ J ]) ] .If condition become true then swapping done between numbers of value [ ( J - 1 ) , J ].
For example :
when I = 1 , J=1 , J-1=0
Condition: [ if (a[ J-1 ] > a[ J ]) ] , i.e a[0]>a[1]
a[0] =17 , a[1] = 19
CASE 1: 17 > 19 : Condition=F : No Swapping between 17 & 19 : J=J+1
a[1]=19 , a[2] =3
CASE 2 : 19 > 3 : Condition=T : Swapping take place between 19 & 3 : J=J+1
New shorted List : 17 , 3 , 19 , 4 , 13
a[2]=19 , a[3] =4
CASE 3: 19 > 4 : Condition=T : Swapping take place between 19 & 4 : J=J+1
New shorted List : 17 , 3 , 4 , 19 , 13
a[3]=19 , a[4] =13
CASE 4: 19 > 4 : Condition=T : Swapping take place between 19 & 13 : J=J+1
New shorted List : 17 , 3 , 4 , 13 , 19 ← First Sorted List
CASE 5: Check Condition : J < = N-I , i.e 5< = 4 : False : Terminate Inner Loop : I= I+1
Now I=2 : J=0 : Do same process as above on Following List :17 , 3 , 4 , 13 , 19
Try your self until not get following list
3 , 4 , 13 , 17 , 19 ← Final Sorted List
Evaluation of Bubble Sort:
There are two cases for evaluating bubble sort:
1. Best Case Complexity For Bubble Sort:
Best Case for bubble sort occur when given array is already sorted in such case bubble sort need only one pass and ( n - 1 ) comparison with complexity.
Ofn = O(n-1)
Now neglect constants
Ofn = O(n)
2. Worst Case Complexity For Bubble Sort:
In worst case if bubble sort need ( n - 1 ) passes as:
1st Pass need n-1 comparisons
2nd Pass need n-1 comparisons
3rd Pass need n-1 comparisons
----- ----
----- ----
( n - 1 ) Pass need 1 comparisons
--------------------------------------------------
Total = 1 + 2 + 3 + ---- ( n - 1 )
--------------------------------------------------
fn = n ( n - 1 ) / 2
fn = n2 / 2 - n / 2
Ofn = O(n2)
It shows the time complexity of bubble sort is n2
No comments:
Post a Comment