## Bubble Sort

Bubble Sort is the simplest sorting algorithm that works by repeatedly **swapping the adjacent elements** if they are in wrong order.

An example of bubble sort. Starting from the beginning of the list, compare every adjacent pair, swap their position if they are not in the right order (the latter one is smaller than the former one). After each iteration, one less element (the last one) is needed to be compared until there are no more elements left to be compared.

From the below animation it can be seen that Bubble sort works fastest for nearly sorted array of elements. The time required to sort the elements increases in the order: few unique, reversed and then random.

**What are random, nearly sorted, reversed and few unique elements?**

**Random:**{6, 9, 5, 8, 7, 4, 2, 1, 3}

Here all the elements are arranged in a random fashion.**Nearly sorted:**{5, 6, 7, 8, 9, 1, 2, 3, 4}

The array is nearly sorted. For example, the above array if divided into two, are sorted individually.**Reversed:**{9, 8, 7, 6, 5, 4, 3, 2, 1}

The array elements are reverse sorted and we are supported to sort them in ascending order.**Few Unique:**{1, 1, 2, 9, 4, 3, 2, 5, 9, 6}

The array contains duplicate entries.

Random |
Nearly Sorted |
Reversed |
Few Unique |

**Key**

- Black values are sorted.
- Gray values are unsorted.
- A red triangle marks the algorithm position.

**Algorithm**

**procedure** bubbleSort( A : list of sortable items )
n = length(A)
** repeat**
** for** i = 1 **to** n-1 **inclusive** **do**
/* if this pair is out of order */
** if** A[i-1] > A[i]** then**
/* swap them */
swap( A[i-1], A[i] )
**end if**
** end for**
**end procedure**

**Implementation:**

voidbubbleSort(intarr[],intn) {inti, j;for(i = 0; i < n; i++) {for(j = 0; j < n-i-1; j++) {if(arr[j] > arr[j+1]) { swap(&arr[j], &arr[j+1]); } } } }

**Optimizing bubble sort**

The bubble sort algorithm can be easily optimized by observing that the n-th pass finds the n-th largest element and puts it into its final place. So, the inner loop can avoid looking at the last n-1 items when running for the n-th time:

**Algorithm**

**procedure** bubbleSort( A : list of sortable items )
n = length(A)
**repeat**
swapped = false
** for** i = 1** to** n-1 **inclusive do
if** A[i-1] > A[i] **then**
swap(A[i-1], A[i])
swapped = true
** end if
end for**
n = n - 1
until not swapped
**end procedure**

**Implementation**

voidbubbleSort(intarr[],intn) {inti, j;boolswapped;for(i = 0; i < n; i++) { swapped =false;for(j = 0; j < n-i-1; j++) {if(arr[j] > arr[j+1]) { swap(&arr[j], &arr[j+1]); swapped =true; } } // IF no two elements were swapped by inner loop, then breakif(swapped ==false)break; } }

**Analysis**

Bubble sort has worst-case and average complexity both *О*(*n*^{2}), where *n* is the number of items being sorted. There exist many sorting algorithms with substantially better worst-case or average complexity of *O*(*n* log *n*). Therefore, bubble sort is not a practical sorting algorithm when *n* is large and should be avoided in the case of large collections. It will not be efficient in the case of a reverse-ordered collection.

The only significant advantage that bubble sort has over most other implementations, is that the ability to detect that the list is sorted is efficiently built into the algorithm. When the list is already sorted (best-case), the complexity of bubble sort is only *O*(*n*). By contrast, most other algorithms, even those with better average-case complexity, perform their entire sorting process on the set and thus are more complex.

The positions of the elements in bubble sort will play a large part in determining its performance. Large elements at the beginning of the list do not pose a problem, as they are quickly swapped. Small elements towards the end, however, move to the beginning extremely slowly. This has led to these types of elements being named rabbits and turtles, respectively.

**Auxiliary Space:** O(1)

**Sorting In Place: **Yes

**Stable:** Yes

Due to its simplicity, bubble sort is often used to introduce the concept of a sorting algorithm.

In computer graphics it is popular for its capability to detect a very small error (like swap of just two elements) in almost-sorted arrays and fix it with just linear complexity (2n). For example, it is used in a polygon filling algorithm, where bounding lines are sorted by their x coordinate at a specific scan line (a line parallel to x axis) and with incrementing y their order changes (two elements are swapped) only at intersections of two lines

Source: Wikipedia