Bubble sort swaps two neighbours whenever the left one is larger. How many swaps does it make to sort n numbers into increasing order? Equal numbers are never swapped.
What to build
A bubble sort that counts every swap it makes.
Requirements
- Sweep through the array, swapping neighbours when the left one is larger.
- Leave equal neighbours as they are.
- Print the total number of swaps.
Input
The first line has n (1 ≤ n ≤ 100). The second line has the n numbers.
Output
The number of swaps.
Constraints
1 ≤ n ≤ 100.
Example
Input:
5
5 1 4 2 8
Output:
4
Why it works
Each swap fixes exactly one pair of numbers that are in the wrong order, so the number of swaps equals the number of such pairs.
Examples
Example 1 · Input
5 5 1 4 2 8
Expected output
4
Example 2 · Input
3 1 2 3
Expected output
0
Hints
Hint 1
Write a normal bubble sort and add 1 to a counter at every swap.
Hint 2
Swap only when a[j] > a[j + 1]: equal neighbours stay as they are.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n;
int a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int swaps = 0;
for (int pass = 0; pass < n - 1; pass++) {
for (int j = 0; j < n - 1 - pass; j++) {
if (a[j] > a[j + 1]) {
int t = a[j];
a[j] = a[j + 1];
a[j + 1] = t;
swaps++;
}
}
}
printf("%d\n", swaps);
return 0;
}