Having been in Java world for around 5 years,
I believe Bubble Sort is the probably simplest and widely used sorting
algorithm that works by repeatedly swapping the adjacent elements if they are not in the right order. However, with just a little tweaking, it’s possible to make it
more efficient. So, we will first see what Bubble Sort algorithm is and then
move to its optimization part.
To
sort the entire array, the array is traversed n-1 time (array having n elements).
These are called passes. In the first pass the largest element moves to the
last position (sorting in ascending order). So if the original (unsorted) array
is:
55 33 99 77
44
During the first iteration, adjacent elements will be compared, and swapped if larger element is on left side), as shown below:
After
first iteration, the largest element is at the last position.
33 55 77 44 99
Now, in the 2nd pass, we will consider the first (n-1)
elements only (because last position already has largest element). After
2nd pass the array will be
33 55 44 77
99
i.e.,
77 will be moved to the (n-1)th position.
After
(n-1) iterations, (n-1) elements will be moved to their proper positions, the
last element has to be the smallest. So the array will be sorted after n-1
passes.
Algorithm:
void bubbleSort(int array[], int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
}
}
Time Complexity: O(n*n)
Auxiliary Space: O(1)
Boundary Cases: Bubble sort
takes minimum time (Order of n) when elements are already sorted.
Sorting In Place: Yes
Stable: Yes
Improvement (Optimization):
In the
above example, the array got sorted after 2nd pass, but we will still continue
with the 3rd, 4th pass. Suppose if the array is already sorted, then there will
be no swapping (because adjacent elements are always in order), but still we
will continue with the passes and there will still be (n-1) passes.
If we
can identify, that the array is sorted, then we should stop execution of
further passes. This is the optimization over the original bubble sort
algorithm.
If there is no swapping in an iteration pass, it means the array
has become sorted, so algorithm should be smart enough to skip further iterations.
For this we can have a flag variable which is set to true before each pass and is made false when a swapping is performed.
void optimizedBubbleSort(int array[], int n) {
for (int i = 0; i < n; i++) {
boolean flag = true;
for (int j = 0; j < n - i - 1; j++) {
if (array[j] > array[j + 1]) {
flag = false;
int temp = array[j + 1];
array[j + 1] = array[j];
array[j] = temp;
}
}
// No Swapping happened, array is
sorted
if (flag) {
return;
}
}
}
For the best case (array already sorted) the optimized
algorithm will be O(n).
For average case also, the performance will see an
improvement. Whereas the original algorithm was O(n2)
for all the cases.
0 comments:
Post a Comment