Lets explain Bubble sort by illustrating tow specific examples involving steps where smaller numbers bubbles to first and when larger numbers bubbles to last.
Number list to sort: 2 5 3 0 6 1
Case 1: Smaller numbers bubbles to first
Step 1: 0 5 3 2 6 1
Step 2: 0 3 5 2 6 1
0 2 5 3 6 1
0 1 5 3 6 2
Step 3: 0 1 3 5 6 2
0 1 2 5 6 3
Step 4: 0 1 2 3 6 5
Step 5: 0 1 2 3 5 6
Case 2: Larger numbers bubbles to first
Step 1: 2 3 5 0 6 1
2 3 0 5 6 1
2 3 0 5 1 6
Step 2: 2 0 3 5 1 6
2 0 3 1 5 6
Step 3: 0 2 3 1 5 6
0 2 1 3 5 6
Step 4: 0 1 2 3 5 6
C Algorithm for Bubble Sort (smaller number bubbles to first)
/* n gives no. of integers */ /* X[] stores integers */ for(i = 0; i < n; i++){ for(j = i + 1; j < n; j++){ if(X[j] < X[i]){ temp = X[j]; X[j] = X[i]; X[i] = temp; } } }
Order of above sorting algorithm: Order = (n-1)n = O(n2)
C Algorithm for Bubble Sort (larger numbers bubbles to last)
/* n gives no. of integers */ /* X[] stores integers */ for(i = 0; i < n; i++){ for(j = i+1; j < n; j++){ if(X[i] > X[j]){ temp = X[j]; X[j] = X[i]; X[i] = temp; } } }
Order of above sorting algorithm: Order = (n-1)n = O(n2)