While solving prog. task with bubble-sort I ran into a problem. So, i need to count the number of swaps in array and the number of passing through array. Actually, there is output. In my code array is being sorted properly but counters are working wrong.
step = int(input())
a = list(map(int, input().split()))
passage_number = 0
swap_number = 0
for x in range(step):
for i in range(step-x-1):
passage_number += 1
if a[i] <= a[i+1]:
a[i], a[i+1] = a[i+1], a[i]
swap_number += 1
print(passage_number, swap_number)
Sample input (two strings), and output:
8
3 1 4 1 5 9 2 6
5 8
(now it returns smth like "21 14" etc, depends on position of variables)
I think that the problem is in incorrect variables position but I can't solve this easy problem for about 6 hours. I tried to set variables ib different positions and to expirement with variable 'step' but all attempts was unsuccessful. I'll be very grateful if you'll show me what should I change in my code to solve this problem (suddenly google has not answer btw :D)
Looks like the task is using the so-called 'modified bubble sort' which utilizes a flag that halts the algorithm if a single pass through it results in no swaps. To implement this you just need to set a flag before the loops begin, have the outer lap reset it, and have any swap flip it, then have a conditional-break statement to test after every passage. The loop section of your code would be something like this:
for x in range(step - 1):
passage_number += 1
flag = True
for i in range(step - 1):
if a[i] > a[i+1]:
a[i], a[i+1] = a[i+1], a[i]
swap_number += 1
flag = False
if flag:
break
That gives 5 8 for your sequence.