Bubble sort is a simple and slow sorting algorithm that **repeatedly steps through the collection, compares each pair of adjacent elements and swaps them if they are in the wrong order**. In the sorting algorithm, if we watch the movements of the elements with higher orders (i.e. larger values), they are like bubbles in the water, floating slowly from the bottom to the top (from one side/middle of the array to the other side of the array).

We can imagine that big bubbles float to the surface on every step and stay there. At the step, when no bubble moves, sorting stops.

## 1. Algorithm

The basic idea of the Bubble Sort algorithm can be described as these steps:

- Data elements are grouped into two sections: a sorted section and an unsorted section.
- Go through every element in the unsorted section and re-arrange its position with its neighbor to put the element in higher order on the higher position. In the end, the element with the highest order will be on top of the unsorted section and moved to the bottom of the sorted section.
- Repeat step 2 until no more elements are left in the un-sorted section.

## 2. Bubble Sort Example

The following code demonstrates to implement and use the bubble sort algorithm in Java.

```
public class BubbleSortExample
{
public static void main(String[] args)
{
// This is unsorted array
Integer[] array = new Integer[] { 12, 13, 24, 10, 3, 6, 90, 70 };
// Let's sort using bubble sort
bubbleSort(array, 0, array.length);
// Verify sorted array
System.out.println(Arrays.toString(array));
}
@SuppressWarnings({ "rawtypes", "unchecked" })
public static void bubbleSort(Object[] array, int fromIndex, int toIndex)
{
Object d;
for (int i = toIndex - 1; i > fromIndex; i--)
{
boolean isSorted = true;
for (int j = fromIndex; j < i; j++)
{
//If elements in wrong order then swap them
if (((Comparable) array[j]).compareTo(array[j + 1]) > 0)
{
isSorted = false;
d = array[j + 1];
array[j + 1] = array[j];
array[j] = d;
}
}
//If no swapping then array is already sorted
if (isSorted)
break;
}
}
}
```

## 3. Performance and Complexity

- Bubble sort belongs to
**O(n2)**sorting algorithms, which makes it**quite inefficient for sorting large data volumes**. - Bubble sort is both stable and adaptive.
**In the case of nearly sorted data, bubble sort takes O(n)**time but requires at least 2 passes through the data.- It can be practical if the input is usually in sort order but may occasionally have some out-of-order elements nearly in position.
- Bubble sort should be avoided in the case of large collections.
- It will not be efficient in the case of a reverse-ordered collection.

Happy Learning !!

## Leave a Reply