Pseudocode:
for j = 0 to n -2 // no need till n-2 as it will validate already properly aligned values(see code)
if a[j] > a[j+1]
swap (a[j], a[j+1])
After the above pass, the largest element will come at the end.
Perform the above pass for each of the elements in the array.
Code
#include <stdio.h>
#define NELEMS(x) (sizeof (x) / sizeof (x[0]))
void display(int arr[], int n)
{
int i;
for (i = 0; i < n; ++i)
printf("%d ", arr[i]);
printf("\n");
}
void swap(int *x, int *y)
{
int t = *x;
*x = *y;
*y = t;
}
void bubble(int arr[], int n)
{
int i, j;
int swapped = 0;
for (i = 0; i < n - 1; ++i) { // no need of <n as bigger will find its way anyway
swapped = 0;
for (j = 0; j < n - i - 1; ++j) { // j < n-2 also works, but this is not needed
if (arr[j] > arr[j + 1]) {
swap(arr + j, arr + j + 1);
swapped = 1;
display(arr, 8);
}
}
if (swapped == 0) break; // if no swap happened, no need to continue any further
}
}
int main()
{
int arr[] = { 17, 21, 19, 15, 5, 99, 1, 0 };
/* int arr[] = { 17, 21, 19, 98, 99, 100, 101, 102 }; // almost sorted (usage of swapped flag helps here) */
printf("Unsorted: ");
display(arr, NELEMS(arr));
bubble(arr, NELEMS(arr));
printf("Sorted: ");
display(arr, NELEMS(arr));
}
Output:
Unsorted: 17 21 19 15 5 99 1 0
17 19 21 15 5 99 1 0
17 19 15 21 5 99 1 0
17 19 15 5 21 99 1 0
17 19 15 5 21 1 99 0
17 19 15 5 21 1 0 99
17 15 19 5 21 1 0 99
17 15 5 19 21 1 0 99
17 15 5 19 1 21 0 99
17 15 5 19 1 0 21 99
15 17 5 19 1 0 21 99
15 5 17 19 1 0 21 99
15 5 17 1 19 0 21 99
15 5 17 1 0 19 21 99
5 15 17 1 0 19 21 99
5 15 1 17 0 19 21 99
5 15 1 0 17 19 21 99
5 1 15 0 17 19 21 99
5 1 0 15 17 19 21 99
1 5 0 15 17 19 21 99
1 0 5 15 17 19 21 99
0 1 5 15 17 19 21 99
Sorted: 0 1 5 15 17 19 21 99
Time Complexity: O(n^n)
