Bubble Sort

DESCRIPTION
This is one of the simplest comparison-based sorting algorithm.
It starts at the beginning of the input array $A$, and compares the first two elements (i.e., $a_1,a_2$), and if $a_1$ is greater than $a_2$ it swaps them.
Bubble Sort keeps doing this for each pair of adjacent elements until it reaches the end of the array. Once the first pass is completed, the algorithm then starts again with the first two elements, repeating until no swaps have occurred on the last pass.

COMPLEXITY ANALYSIS
This algorithm’s average and worst case time complexity is $O(n^2)$, so it is rarely used to sort large, unordered data sets. In fact, Bubble Sort can be used to sort a small number of items or a list of items of arbitrary length that are nearly sorted (i.e., so that very few items are out of place).
Since the algorithm works in-place, no extra memory is needed, thereby its space complexity is constant $O(1)$.

IMPLEMENTATION (Java)

```public static void bubbleSort(int[] a) {

if(a==null || a.length==1) {
return; // simply return if the input array is either null or contains only one element
}
int size = a.length;
int tmp;
boolean toSwap = true;
// loop until an entire scan of the array requires no swap
while(toSwap) {
toSwap = false;
// linear scan of the input array
for(int i=0; i < size-1; ++i) {
if(a[i+1] < a[i]) { // swap two adjacent elements if they are in the wrong order
tmp = a[i];
a[i] = a[i+1];
a[i+1] = tmp;
toSwap = true;
}
}
}
}
```

IMPLEMENTATION (Python)

```
def bubble_sort(a):

# base cases
if not a or len(a) == 0:
return
if len(a) == 1:
return
else:
to_swap = True
# loop until an entire scan of the array requires no swap
while to_swap:
to_swap = False
i = 0
# linear scan of the input array
while i < len(a) - 1:
if a[i] > a[i+1]: # swap two adjacent elements if they are in the wrong order
tmp = a[i]
a[i] = a[i+1]
a[i+1] = tmp
to_swap = True
i += 1
return
```