**Introduction**

The article discusses the basic __Sorting__ algorithms with the time complexity of quadratic (O(N^{2})) or worse. The algorithms discussed are bubble sort, selection sort and insertion sort. We will be covering the algorithms along with their pseudocode, the C++ code and the best, worst and average-case time complexity.

**Bubble Sort**

This algorithm sorts the array by continuously swapping adjacent elements. The larger of the two numbers gets swapped to the right. This way, we bubble the larger numbers to the right of the array. During the first pass of the inner loop, the largest number gets bubbled to the right, and we end up with n-1 unsorted elements. We repeat the above process for n-1 elements now. Every pass, we similarly reduce the size of the unsorted array and stop when the size reduces to 1, as a single element by itself is always sorted.

We could make the algorithm slightly better by ending the execution if we didn't have any swaps in the inner array (implying that the part we assumed unsorted was already sorted).

For example,

```
a[] = [4, 2, 3, 1]
=> [4, 2, 3, 1], 4 > 2 so we swap
=> [2, 4, 3, 1], 4 > 3, swap
=> [2, 3, 4, 1], 4 > 1 swap
=> [2, 3, 1, 4], 2 < 3 donâ€™t swap
=> [2, 3, 1, 4], 1 < 3, swap
=> [2, 1, 3, 4], 1 < 2, swap
=> [1, 2, 3, 4], the array is sorted
```

**Pseudocode**

```
func bubble_sort(a, n)
for i from 0 to n-2:
count_swaps = 0
for j from 0 to n - i - 2:
If a[j] is greater than a[j+1]:
swap(a[j], a[j+1])
increase count_swaps by 1
If count_swaps is 0:
// breaks out of the outer loop
break
```

**Code in C++**

```
#include <bits/stdc++.h>
using namespace std;
void bubble_sort(int a[], int n){
for(int i = 0; i < n - 1; i++){
int count_swaps = 0;
for(int j = 0; j < n - i - 1; j++){
if(a[j] > a[j+1]){
swap(a[j], a[j+1]);
count_swaps += 1;
}
}
if(!count_swaps) break;
}
}
void print_arr(int a[], int n){
for(int i = 0; i < n; i++){
cout << a[i] << " ";
}
cout << "\n";
}
int32_t main(){
int a[] = {5, 4, 3, 2, 1, 0};
int n = sizeof(a) / sizeof(a[0]);
cout << "Unsorted Array\n";
print_arr(a, n);
bubble_sort(a, n);
cout << "Sorted Array\n";
print_arr(a, n);
}
```

**Output**

```
Unsorted Array
5 4 3 2 1 0
Sorted Array
0 1 2 3 4 5
```

**Time Complexity**

The time complexity of the algorithm is of the order of O(N^{2}) in the worst case (when the input is sorted in reverse order).similarly, in the average case it is O(N^{2}) (as the average inversion count is also (N*(N-1))/4). And O(N) in the best case (when the array is already sorted).

**Space Complexity**

The algorithm requires an extra O(1) space.

Also see, __Longest Common Substring____ __and __Rabin Karp Algorithm__