Bubble Sorting
Statement
Goal
Bubble Sort is an algorithm for sorting a list of numbers, where pairs of adjacent elements are checked and swapped if they aren't in order.Your job is to count the number of swaps taken to sort a list using the Bubble Sort algorithm.
For example, if the input is
4, 3, 2, 1 --> 3, 4, 2, 1
3, 4, 2, 1 --> 3, 2, 4, 1
3, 2, 4, 1 --> 3, 2, 1, 4
This pass made 3 swaps.
The next pass will be:
3, 2, 1, 4 --> 2, 3, 1, 4
2, 3, 1, 4 --> 2, 1, 3, 4
2, 1, 3, 4 (No swap)
This pass made 2 swaps.
The next pass is:
2, 1, 3, 4 --> 1, 2, 3, 4
1, 2, 3, 4 (No swap)
1, 2, 3, 4 (No swap)
This pass made 1 swap.
The next pass is:
1, 2, 3, 4 (No swap)
1, 2, 3, 4 (No swap)
1, 2, 3, 4 (No swap)
This pass made no swaps, which terminates the Bubble Sort algorithm.
Then, the total number of swaps is 3 + 2 + 1 which is
Input
Line 1: N, the length of the list
Line 2: A list of N numbers to be sorted
Line 2: A list of N numbers to be sorted
Output
A single line containing the number of swaps that bubble sort will take to sort the list to ascending order.
Constraints
0 < N < 100
For each i in the list:
-1000 < i < 1000
For each i in the list:
-1000 < i < 1000
Example
Input
4 4 3 2 1
Output
6
Game modes
Fastest, Shortest
Test cases
Example Test
Input
4
4 3 2 1
Output
6
Descending Validator
Input
5
7 6 5 4 3
Output
10
Already Sorted Test
Input
10
-9 -7 0 0 1 5 9 10 11 99
Output
0
Pretty Much Already Sorted Validator
Input
8
-9 -8 -7 1 -1 7 8 9
Output
1
Many Duplicates Test
Input
20
5 5 5 5 5 4 4 4 4 4 3 3 3 3 3 2 2 2 2 2
Output
150
Many Duplicates Validator Validator
Input
13
-10 -10 -10 5 5 5 -10 -10 -10 5 5 5 1
Output
15
Long List Test
Input
38
55 38 47 120 29 9 10 33 55 28 10 20 90 98 76 65 33 39 -39 39 -39 22 21 55 83 98 82 43 23 13 16 788 484 288 233 108 12 567
Output
283
Long List Validator Validator
Input
30
10 9 8 7 6 5 4 5 10 19 80 6 8 1 2 4 5 8 -9 -5 43 1 3 4 2 9 9 9 23 99
Output
214
Solution language
Solution
Stub generator input