Bubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in which each pair of adjacent elements is compared and the elements are swapped if they are not in order. This algorithm is not suitable for large data sets as its average and worst case complexity are of Ο(n2) where n is the number of items.
How Bubble Sort Works?
We take an unsorted array for our example. Bubble sort takes Ο(n2) time so we're keeping it short and precise.
14
|
33
|
27
|
35
|
10
|
Bubble sort starts with very first two elements, comparing them to check which one is greater.
14
|
33
|
27
|
35
|
10
|
In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we compare 33 with 27.
14
|
33
|
27
|
35
|
10
|
We find that 27 is smaller than 33 and these two values must be swapped. And new array looks like
14
|
27
|
33
|
35
|
10
|
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, the array should look like this –
14
|
27
|
33
|
10
|
35
|
Same procedure we have to apply to sort the array and sorted array will like following
10
|
14
|
27
|
33
|
35
|
C# program
using System;
class bubblesort
{
static void Main(string[] args)
{
int[] a = { 14, 33, 27, 35, 10 };
int t;
Console.WriteLine("The Array is : ");
for (int i = 0; i < a.Length; i++)
{
Console.WriteLine(a[i]);
}
for (int j = 0; j <= a.Length - 2; j++)
{
for (int i = 0; i <= a.Length - 2; i++)
{
if (a[i] > a[i + 1])
{
t = a[i + 1];
a[i + 1] = a[i];
a[i] = t;
}
}
}
Console.WriteLine("The Sorted Array :");
foreach (int aray in a)
Console.Write(aray + " ");
Console.ReadLine();
}
}
|
Complexity Analysis of Bubble Sort
In Bubble Sort, n-1 comparisons will be done in the 1st pass, n-2 in 2nd pass, n-3 in 3rd pass and so on. So the total number of comparisons will be,
(n-1) + (n-2) + (n-3) + ..... + 3 + 2 + 1
Sum = n(n-1)/2
i.e O(n2)
Hence the time complexity of Bubble Sort is O(n2).
The main advantage of Bubble Sort is the simplicity of the algorithm.
The space complexity for Bubble Sort is O(1), because only a single additional memory space is required i.e. for temp variable.
Also, the best case time complexity will be O(n), it is when the list is already sorted.
Following are the Time and Space complexity for the Bubble Sort algorithm.
- Worst Case Time Complexity [ Big-O ]: O(n2)
- Best Case Time Complexity [Big-omega]: O(n)
- Average Time Complexity [Big-theta]: O(n2)
- Space Complexity: O(1)
EmoticonEmoticon