Bubble Sort – Bubble sort algorithm
uses by relocating the largest element at the highest index in the array. Bubble sort is a simple sorting
algorithm. The algorithm starts at the beginning of the data set. It compares
the first two elements, and if the first is greater than the second, it swaps
them. It continues doing this for each pair of adjacent elements to the end of
the data set. It then starts again with the first two elements, repeating until
no swaps have occurred on the last pass.
•
Let
n = array length = size of the array
•
The
outer loop is executed n-1 times
•
Each
time the outer loop is executed, the inner loop is executed
•
Inner
loop executes n-1 times at first, linearly dropping to just once
•
On
average, inner loop executes about n/2 times for each execution of the outer
loop
•
In
the inner loop, the comparison is always done (constant time), the swap might
be done (also constant time)
•
Result
is n * n/2 * k, that is, O(n2/2 + k) = O(n2)
Complexity :
Best-Case Analysis
•
If
the elements start in sorted order, the for loop will compare the adjacent
pairs but not make any changes
•
So
the swapped Elements variable will still be false and the while loop is only
done once
•
There
are N – 1 comparisons in the best case
Worst-Case Analysis
•
If
in the best case the while loop is done once, in the worst case the while loop
must be done as many times as possible
•
Each
pass of the for loop must make at least one swap of the elements
•
The
number of comparisons will be:
Average-Case Analysis
•
We
can potentially stop after any of the (at most) N – 1 passes of the for loop
•
This
means that we have N – 1 possibilities and the average case is given by where
C(i) is the work done in the first i passes
•
On
the first pass, we do N – 1 comparisons
•
On
the second pass, we do N – 2 comparisons
Working Example.
Array
a[5] having 5 element starting from index 0 to 4.
Values
stored in a[]={5 ,3, 9, 8, 2}
The
passes will take place for the bubble sort –
Element
Position
|
0
|
1
|
2
|
3
|
4
|
Largest Element
|
Pass-1
|
a[0]>a[1]
|
a[1]>a[2]
|
a[2]>a[3]
|
a[3]>a[4]
|
9
|
|
5
|
3
|
9
|
8
|
2
|
||
3
|
5
|
9
|
8
|
2
|
||
3
|
5
|
9
|
8
|
2
|
||
3
|
5
|
8
|
9
|
2
|
||
3
|
5
|
8
|
2
|
9
|
||
Pass-2
|
3
|
5
|
8
|
2
|
8
|
|
3
|
5
|
8
|
2
|
|||
3
|
5
|
2
|
8
|
|||
5
|
||||||
Pass-3
|
3
|
5
|
2
|
|||
3
|
2
|
5
|
||||
Pass-4
|
3
|
2
|
3
|
|||
2
|
3
|
|||||
Final
Positions of the Element
|
2
|
3
|
5
|
8
|
9
|
Algorithm
for i ←
0 to n-1
do
for j ← 0 to n-i-1
do
If A[j] > A[j-1] then
A[j-1]↔ A[j]
end for j
end for i
Source Code
import java.io.*;
public class Bubble_Sort
{
public static void main(String
args[])throws IOException
{
BufferedReader br=new
BufferedReader(new InputStreamReader(System.in));
int Size;
System.out.print("\n\tEnter Size : ");
Size=Integer.parseInt(br.readLine());
int AR[]=new int[Size];
Bubble_Sort BS=new
Bubble_Sort();
BS.Accept(AR,Size);
System.out.print("\n\tOriginal Data : \t");
BS.Display(AR,Size);
BS.Sort(AR,Size);
System.out.print("\n\tAfter Sort : \t");
BS.Display(AR,Size);
}
void Sort(int AR[], int Size)
{
for(int i=0;i<Size;i++)
{
for(int j=0;j<Size-i-1;j++)
{
if(AR[j]>AR[j+1])
{
AR[j]=AR[j]+AR[j+1]; //Swapping
AR[j+1]=AR[j]-AR[j+1];
AR[j]=AR[j]-AR[j+1];
}
}
}
}
void Display(int AR[],int Size)
{
for(int i=0;i<Size;i++)
{
System.out.print(AR[i]+" ");
}
System.out.println();
}
void Accept(int AR[], int
Size)throws IOException
{
BufferedReader br=new
BufferedReader(new InputStreamReader(System.in));
for(int i=0;i<Size;i++)
{
System.out.print("\tEnter AR["+(i+1)+"] : ");
AR[i]=Integer.parseInt(br.readLine());
}
}
}
Output
Enter
Size : 5
Enter
AR[1] : 5
Enter
AR[2] : 3
Enter
AR[3] : 9
Enter
AR[4] : 8
Enter
AR[5] : 2
Original
Data : 5 3 9
8 2
After
Sort : 2
3 5 8
9
No comments:
Post a Comment