Bubble Sort is one of the simplest sorting algorithms that works by comparing each pair of adjacent elements and swapping them if they are in wrong order. Unfortunately this is the worst algorithm due to its *O(N²)* time complexity on average.

You can read about other popular sorting algorithms here.

Time complexity :O([Best -- Average -- Worst] Memory :N —N² —N²)O(1)i.e. just the input array Stable : Yes # N being the number of elements in the list

**Usage:**

1. When you want to implement some sorting algorithm very quickly not bothering about anything else. This is not at all practical when N is large.

2. Only advantage it has over most other sorting algorithms, even **quicksort**, but not **insertion sort** is to efficiently detect whether the list is already sorted or not. When the list is already sorted the complexity is O(N) (best case).

**Bottom line: **Use this when you know that the list is almost-sorted (It can fix this just with linear complexity O(2N))

**Implementation in C:**

**Question:** Sort an array of integers in increasing order using bubble sort algorithm (format similar to most of the online programming contests )

**Input: **

First line of the input contains T, number of test cases

Each test case contains an integer N ≤ 200, the number of integers in that array, followed by N integers separated by N spaces.

**Output:** Sorted array

**Sample Input**

3 5 4 7 9 3 1 3 4 5 5 4 6 10 6 7

**Sample Output**

1 3 4 7 9 4 5 5 6 6 7 10

**Code**

Brief explanation is given in the gist.