Bubble sort quiz: why the result is not the same?

[lupoalberto]

Here's a quiz of a Math professor on Twitter:



He says the results are:
1) 1 / 930
2) 1 / 14880

I did this code (python3) and while the first result is the same, the second is not the same.
I don't understand why the 2nd answer with my code is about 0.002.
I investigated my script for hours and i don't find any mistake...

Do you confirm that the code is right?

import random

def bubblesortOnePass(l):
    if len(l) == 1:
        return l
    else:
        for i in range(len(l)):
            try:
                if l[i] > l[i+1]:
                    l[i], l[i+1] = l[i+1], l[i]
            except:
                if l[-2] > l[-1]:
                    l[-2],l[-1] = l[-1],l[-2]
        return l

def bubblesortTwoPass(l):
    global counter
    if len(l) == 1 or counter == 2:
        return l
    else:
        for i in range(len(l)):
            try:
                if l[i] > l[i+1]:
                    l[i], l[i+1] = l[i+1], l[i]
            except:
                if l[-2] > l[-1]:
                    l[-2],l[-1] = l[-1],l[-2]
        counter += 1
        return bubblesortTwoPass(l[:-1]) + [l[-1]]

def generateList():
    L = []
    remaining = [i for i in range(1,41)]
    while len(L) < 40:
        random_N = random.choice(remaining)
        L.append(random_N)
        remaining.remove(random_N)
    return L

N = 1000000
totalOnePass = 0
totalTwoPass = 0
for i in range(N):
    L = generateList()
    f = L[19]
    K = L.copy()
    bubblesortOnePass(L)
    if f == L[29]:
        totalOnePass += 1
    counter = 0
    After2pass = bubblesortTwoPass(K)
    if f == After2pass[29]:
        totalTwoPass += 1

print("Probability after One Pass is {}".format(float(totalOnePass / N)))
print("Probability after Two Pass is {}".format(float(totalTwoPass / N)))

[IAMK]

Are you sure you're doing it properly?
This sounds like a theoretical question, as opposed to a brute force question.
Refer to: Link

Also, I'm no python expert, but some things I believe can be improved:
1- bubblesortOnePass()'s return value is never used, so you don't need to return l.
2- Is it good to define a local counter in line 50, then a global counter in line 17?
3- range(len())
4- Since you pass K into bubblesortTwoPass(), I would use k, as opposed to l inside the function.
5- If I had to guess, the problem might be line 29.

[nilamo]

3- range(len())

range(len()) is probably fine in this case, as they're purposefully mutating the list via indices. Though, it would probably be clearer if it was just a while loop with an index counter that was manually incremented.

[lupoalberto]

1- bubblesortOnePass()'s return value is never used, so you don't need to return l.

Yes, you're right, that function was the bubble sort recursive function.
Then i modified it and i transformed it into another non recursive function with only one pass.
So i must remove that condition.

2- Is it good to define a local counter in line 50, then a global counter in line 17?

I did in this way because the variable counter inside the function is "hooked" at the counter variable outside the function.
And every time the recursive function restarts, that variable doesn't come back to zero.
It comes back to zero only when the step of loop outside the function ends and a new step starts.
But i've been coding only for 4 months, so i'm not sure this is an elegant solution.

5- If I had to guess, the problem might be line 29.

mmm.... if i write this list for example:

new = [9,2,8,1,7] 

and i pass it to the bubblesortTwoPass function in this way:

after2pass = bubblesortTwopass(new)
print(after2pass)

Output:
[2,1,7,8,9]

So the algorithm is right.

But i don't understand why if i write:

bubblesortTwopass(new)
print(new)

the output is

Output:
[2,8,1,7,9]

in other words i obtain the bubble sort after only the first pass without the second.

[ljmetzger]

I don't know what the problem is, but the code definitely does not return the theoretical results for Pass 2. When creating code like this, you should try to estimate what the output should look like. Since you have theoretical answers, the expected values should be (for 1,000,000 iterations):
Pass1: 1 /930 = 107.5 (and my results were 1092 - which I consider an acceptable answer)
Pass2: 1/ 14880 = 1/16th of 1 /930 = 67.2 (and my results were 2079 = not acceptable)

Using random numbers makes a solution more difficult, because the answer is different each time. I suggest you either use a fixed list for testing, or use a random number seed for testing purposes only. For example:

random.seed(12345)

For more information about Python random numbers see: https://python-forum.io/Thread-Proposed-...and-Python

I suggest you proceed as follows with concentration on the Pass2 algorithm:
a. Use a preset list as suggested above.
b. Reduce the number of items in the array to 5 or 10.
c. Verify that Pass2 performs an accurate sort, by testing Pass2 by itself (print the list after each iteration).
d. When c. is successful, test with a 40 item list, then test with a random list.

If you need additional help, post the 'original question' in this thread.

Lewis

[lupoalberto]

Lewis

This is the problem:
A given sequence r1, r2, . . . , rn of distinct real numbers can be put in ascending order by means
of one or more “bubble passes”. A bubble pass through a given sequence consists of comparing the
second term with the first term, and exchanging them if and only if the second term is smaller, then
comparing the third term with the second term and exchanging them if and only if the third term
is smaller, and so on in order, through comparing the last term, rn, with its current predecessor and
exchanging them if and only if the last term is smaller.
The example below shows how the sequence 1, 9, 8, 7 is transformed into the sequence 1, 8, 7, 9
by one bubble pass. The numbers compared at each step are underlined.

1 9 8 7
1 9 8 7
1 8 9 7
1 8 7 9

Suppose that n = 40, and that the terms of the initial sequence r1, r2, . . . , r40 are distinct from
one another and are in random order.
1)Find the probability that the number that begins as r20 will end up, after one bubble pass, in the 30th place.
2)Find the probability that the number that begins as r20 will end up, after second bubble pass, in the 30th place.

Honestly my algorithm for the second question (i've no problem for the first question)seems to work well:

def bubblesortTwoPass(l):
    global counter
    if len(l) == 1 or counter == 2:
        return l
    else:
        for i in range(len(l)):
            try:
                if l[i] > l[i+1]:
                    l[i], l[i+1] = l[i+1], l[i]
            except:
                if l[-2] > l[-1]:
                    l[-2],l[-1] = l[-1],l[-2]
        print("After pass {}: {}".format(counter+1, l ))
        counter += 1
        return bubblesortTwoPass(l[:-1]) + [l[-1]]

List1 = [1,9,5,3]
List2 = [8,3,10,2,5]
List3 = [6,2,7,1]

counter = 0
print("After Two pass:",bubblesortTwoPass(List1),'\n')
counter = 0
print("After Two pass:",bubblesortTwoPass(List2),'\n')
counter = 0
print("After Two pass:",bubblesortTwoPass(List3),'\n')

Output:
After pass 1: [1, 5, 3, 9]
After pass 2: [1, 3, 5]
After Two pass: [1, 3, 5, 9]

After pass 1: [3, 8, 2, 5, 10]
After pass 2: [3, 2, 5, 8]
After Two pass: [3, 2, 5, 8, 10]

After pass 1: [2, 6, 1, 7]
After pass 2: [2, 1, 6]
After Two pass: [2, 1, 6, 7]


Process returned 0 (0x0)        execution time : 0.068 s
Premere un tasto per continuare . . .

[ljmetzger]

Your code seems a little complicated, but I agree with your answers.

For 1,000,000 passes I got the following results using my code:

Output:
Pass 1   1090 counts   Frequency 0.00109
Pass 2   2042 counts   Frequency 0.00204

You do not need two algorithms. You could use something like:

import random
 
def bubble_sort_one_pass(a, pass_number):
    n = len(a)
 
    # Subtract 1 because arrays are '0 based' and Pass 1 uses index 0
    i = pass_number - 1
    for j in range(0, n-i-1):
        if a[j] > a[j+1] :
            a[j], a[j+1] = a[j+1], a[j]
    return(a)

    def generateList():
    L = []
    remaining = [i for i in range(1,41)]
    while len(L) < 40:
        random_N = random.choice(remaining)
        L.append(random_N)
        remaining.remove(random_N)
    return L
 
N = 1000000
totalOnePass = 0
totalTwoPass = 0
for i in range(N):
    L = generateList()
    f = L[19]

    pass_number = 1
    L = bubble_sort_one_pass(L, pass_number)
    if f == L[29]:
        totalOnePass += 1

    pass_number = 2
    L = bubble_sort_one_pass(L, pass_number)
    if f == L[29]:
        totalTwoPass += 1
print("Probability after One Pass is {}".format(float(totalOnePass / N)))
print("Probability after Two Pass is {}".format(float(totalTwoPass / N))) 

Lewis

[lupoalberto]

Lewis

So do you believe like me that the answer 1/ 14880 is wrong, right?

[ljmetzger]

do you believe like me that the answer 1/ 14880 is wrong, right?

I could not verify the 1 / 14,880 result, and my independent coding matched your original results.

Unless we both read the problem incorrectly, i believe 1 /14,880 is wrong.

Lewis

[nilamo]

def generateList():
    L = []
    remaining = [i for i in range(1,41)]
    while len(L) < 40:
        random_N = random.choice(remaining)
        L.append(random_N)
        remaining.remove(random_N)
    return L

If you're already using the random module, why not just let it generate a random sequence for you?

>>> import random
>>> items = list(range(1, 41))
>>> random.shuffle(items)
>>> items
[9, 32, 23, 17, 6, 31, 16, 36, 4, 22, 8, 30, 11, 25, 19, 39, 12, 2, 29, 20, 34, 40, 15, 7, 24, 35, 26, 28, 38, 14, 21, 5, 10, 13, 37, 18, 3, 27, 33, 1]
>>> # or
...
>>> random.sample(range(1, 41), 40)
[6, 5, 20, 22, 40, 17, 29, 37, 36, 1, 28, 9, 30, 19, 38, 27, 39, 14, 24, 18, 13, 4, 15, 7, 8, 33, 2, 26, 35, 34, 10, 3, 21, 23, 31, 12, 16, 11, 32, 25]