Table of Contents
Introduction
Bubble Sort is one of the easiest and most used sorting techniques in computation languages. It operates in pairs and swaps the smaller or bigger element. It continues this until one value is sorted throughout the array. In the second pass, it sorts the second value, and so on.
Algorithm
The working method of Bubble Sort is described as follows:
For example, we have the following set of numbers: 2, 67, 39, 1
First Pass
- It will check the first two values to assess which one is smaller. As 2 is smaller than 67, it will stay as it is.
- The next two numbers are 67 and 39. The two numbers will be swapped.
- Similarly, 67 and 1 will be swapped.
So now we have 2, 39, 1, 67
Second Pass
- 1 will be swapped with 39.
We now have 2, 1, 39, 67
Third Pass
- 2 will be swapped with 1.
Fourth Pass
- Although the list has been sorted, the program will iterate one last time. If it finds no swaps to perform, this will indicate the stopping point of the loop.
The Sorted Loop is: 1, 2, 39, 67
Time Complexity
Time Complexity can be defined as the amount of time that is required by the program to completely execute itself. It is measured in Big0() notation.
- Worst Case Time Complexity: O (n*n) This happens when the entire array is reverse sorted. This also happens to be the Average Time Complexity.
- Best Time Complexity: O (n) when the array is already sorted.
Example and Code
class BubbleSort
{
void bubSort (int arr[])
{
int n = arr.length;
for(int i = 0; i < n-1; i++)
for(int j = 0; j < n-i-1; j++)
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
void printArr( int arr[] )
{
int n = arr.length;
for (int i=0; i<n; i++)
System.out.println(arr[i] + “ ”);
System.out.println ();
}
public static void main (String args [])
{
BubbleSort onj = new BubbleSort();
int arr[] = {55, 67, 3, 60, 99, 121}
obj.bubbleSort(arr);
System.out.println (“The Sorted array is as follows ”);
obj.printArr ( arr );
}
}
OUTPUT
3
55
60
67
99
121
0 Comments