1. Principle of the Bubble Sort
Compare two values, and think as if the smaller value among those value floats up like a bubble. (You could also see the contents about Insertion Sort)
2. Algorithm of the Bubble Sort
2.1 Method 1
void bubbleSort(int arr[], int n) { for (int i=0; i < n-1; i++) bubble(arr, i, n); }
void bubble(int arr[], int n) { int temp; for(int j=0; j<n-1-i; j++) { if(arr[j] > arr[j+1]) { //swap temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } }
2.2 Method 2
void bubbleSort(int arr[], int n) { for (int i=0; i<n-1; i++) { for(int j=0; j<n-1-i; j++) { if(arr[j] > arr[j+1]) { //swap temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } }
– n-1-i
In the bubble sort, The biggest value is always placed at the last index. It means the last value of the array always locates in the sorted area.
Therefore in the next iteration, we do not need to compare the last value again. That is how we reduce components that we should have to check to see if it is sorted or not.
– n-i
If use n-i, not n-1-i, It might cause the error (out of range).
More information: Bubble sort