Bubble Sort

Bubble Sort Visualization

Simplest Version

template <typename eType>
void bubbleSort(int vector<eType> arr, int size) {
  int i, j, tmp;
  for (j = 1; j < size; j++) {
    for (i = 0; i < size - j; i++)
      if (arr[i] > arr[i + 1]) {
        tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
      }
  }
}

Best Case Friendly Version

template <typename eType>
void bubbleSort(int vector<eType> arr, int size) {
  int i, j, tmp;
  for (j = 1; j < size; j++) {
    bool flag = false;
    for (i = 0; i < size - j; i++)
      if (arr[i] > arr[i + 1]) {
        tmp = arr[i];
        arr[i] = arr[i + 1];
        arr[i + 1] = tmp;
        flag = true;
      }
    if (!flag) break;
  }
}

Worst case complexity:

$$(\mathrm{N}-1)+(\mathrm{N}-2)+(\mathrm{N}-3) \ldots+1=\sum_{i=1}^{N-1} i =\frac{N \cdot(N-1)}{2}=\mathrm{O}\left(\mathrm{N}^{2}\right)$$