Different recursion result from python 2.7.6 and 3.3.3

Question

I am writing a simple sorting code by recursion, and I test it in Python 2.7.6 and Python 3.3.3. But I obtained two different results. The code is following.

import math, copy, random, sys
call_count = 0;    # Keep track of number of times of stooge_sort() get called
swap_count = 0;    # Keep track of number of times swapping.
def stooge_sort(a, origin):
    global call_count, swap_count;
    call_count += 1;
    n = len(a);
    m = int(math.ceil(n*2/3));
    if(n == 2 and a[0] > a[1]):
        a[0], a[1] = a[1], a[0];
        swap_count += 1;
    elif (n > 2):
        first = copy.deepcopy(a[0:m]);
        a[0:m] = stooge_sort(first, origin);
        second = copy.deepcopy(a[n-m:]);
        a[n-m:] = stooge_sort(second, origin);
        first = copy.deepcopy(a[0:m]);
        a[0:m] = stooge_sort(first, origin);
    return a;

a = [int(random.random() * 100) for i in range(10)];
stooge_sort(a, a);
print("sort function call count = " + str(call_count))
print("swap count = " + str(swap_count));

1) if I run in Python 2.7.6, I would get incorrect sorting and

sort function call count = 40
swap count = 2

2) if I run in Python 3.3.3, I get correct sorting and

sort function call count = 364
swap count = 18

So I wonder which part went wrong in Python 2.7.6?

Just a hunch: [Division in Python 2 vs Python 3](http://www.informit.com/articles/article.aspx?p=1439189) — Lukas Graf, Mar 08 '14 at 15:24

score 5 · Accepted Answer · edited May 23 '17 at 12:20

5

Its all because of this line

m = int(math.ceil(n*2/3));

In Python 2, n*2/3 gives you a value which is 1 lesser than the actual value since the floating point value is truncated (since / does floor division in Python 2.x), but in Python 3, it will do the proper floating point division.

To make the program behave consistently, just make sure that you are using floating point numbers

m = int(math.ceil(n*2.0/3.0))

edited May 23 '17 at 12:20

Community

1
1

answered Mar 08 '14 at 15:24

thefourtheye

233,700
52
457
497

2

`n*2/3` is not the same as `n*(2/3)`. The latter is always 0 as you say, but the former (OP's version) is "only" off by one for many values of n. – Mar 08 '14 at 15:32
@delnan Oh yeah... Thanks for spotting that :) I fixed the xplanation. – thefourtheye Mar 08 '14 at 15:34

score 0 · Answer 2 · answered Mar 08 '14 at 15:32

As others have pointed out, your expression int(math.ceil(n*2/3)) depends on how the / operator is defined, and that changed between Python 2 and Python 3.

In Python 2.2 and later, you can also add this to the beginning of your program:

from __future__ import division

which will cause / to always perform floating point division, regardless of its operands. The // operator will always perform integer division, whether or not you use the above __future__ import (although it is only necessary when using it).

score 0 · Answer 3 · answered Mar 08 '14 at 15:32

In Python, to keep you code unambiguous between versions, use // for floor division, and ensure you have a float for classic division:

Floor division (from Python 3.3 interpreter):

>>> 1//2
0
>>> 2//2
1

True division (from Python 2.7 interpreter):

>>> float(1)/2
0.5

For 2.7, you can also do:

>>> from __future__ import division
>>> 1/2
0.5

Different recursion result from python 2.7.6 and 3.3.3

3 Answers3