C++ Bubble Sort

Introduction

Bubble sort is a simple sorting algorithm that repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order.
In each round, the largest element will "bubble" to the end of the list.

Suppose the list arr is {5, 3, 8, 6, 2}. Number of elements n is 5.
In the first round, it will loop from 1 to n-1, and compare arr[i] and arr[i+1].
In the second round, it will loop from 1 to n-2, and compare arr[i] and arr[i+1].
And so on, until the last round, it will loop from 1 to 2, and compare arr[1] and arr[2].

Implementation

Nested loop is used in bubble sort. The "outer" loop i can be see as "how many times to go through the list"
And the "inner" loop j is "range of elements to check in each loop".

For example, if the list has 5 elements, the outer loop will be 4 times (1 to 4).
After 1st round: arr[5] will be the largest element.
After 2nd round: arr[4] will be the second largest element.
After 3rd round: arr[3] will be the third largest element.
After 4th round: arr[2] will be the fourth largest element.

So arr[1] will be the smallest element. No need to check.

And the inner loop will be repeated 4 times.
During 1st round: Check 4 times. (arr[1] and arr[2]), (arr[2] and arr[3]), (arr[3] and arr[4]) and (arr[4] and arr[5])
During 2nd round: Check 3 times. (arr[1] ad arr[2]), (arr[2] ad arr[3]), (arr[3] ad arr[4])
During 3rd round: Check 2 times. (arr[1] ad arr[2]), (arr[2] ad arr[3])
In the 4th round, Check only once. (arr[1] ad arr[2])

As value of j changes in each round, we use i to control the range of j.

for i = 1 to n-1			// from 1 to 4
  for j = 1 to n-i			// 1st round: 1 to 4, 2nd round: 1 to 3 ...
	if arr[j] > arr[j+1]		// if larger than next element
	  swap(arr[j], arr[j+1])	// swap
	

#include <iostream>
using namespace std;
int main(){
  int arr[] = {5, 3, 8, 6, 2};
  int n = 5, i, j;

  // bubble sort here


  // output the sorted array
  for(int i = 0; i < n; i++){
	cout << arr[i] << " ";
  }