CODEWITHSUNDEEP
python
user466534
user466534

Reputation:

python code understanding

I have following code

def compare_and_swap(x, a, b):
    if x[a] > x[b]:
        x[a], x[b] = x[b], x[a]

def oddeven_merge(x, lo, hi, r):
    step = r * 2
    if step < hi - lo:
        oddeven_merge(x, lo, hi, step)
        oddeven_merge(x, lo + r, hi, step)
        for i in range(lo + r, hi - r, step):
            compare_and_swap(x, i, i + r)
    else:
        compare_and_swap(x, lo, lo + r)

def oddeven_merge_sort_range(x, lo, hi):
    """ sort the part of x with indices between lo and hi.

    Note: endpoints (lo and hi) are included.
    """
    if (hi - lo) >= 1:
        # if there is more than one element, split the input
        # down the middle and first sort the first and second
        # half, followed by merging them.
        mid = lo + ((hi - lo) / 2)
        oddeven_merge_sort_range(x, lo, mid)
        oddeven_merge_sort_range(x, mid + 1, hi)
        oddeven_merge(x, lo, hi, 1)

def oddeven_merge_sort(x):
    oddeven_merge_sort_range(x, 0, len(x)-1)

>>> data = [4, 3, 5, 6, 1, 7, 8]
>>> oddeven_merge_sort(data)
>>> data
[1, 2, 3, 4, 5, 6, 7, 8]

Everything is clear for me ,but only this line can't understand well

 for i in range(lo + r, hi - r, step):

How can I read it using pseudo code?or in other languages for instance C++?

Upvotes: 2

Views: 137

Answers (5)

Karl Knechtel
Karl Knechtel

Reputation: 61654

How can I read it using pseudo code?

Python is very close to being pseudocode.

for i in range(lo + r, hi - r, step):

means exactly what it says: do the following code with each value of i in the specified range. The first two values are the lower and upper bounds of the range, and the step is the distance between values to use. For more information, try help(range) at the Python interpreter prompt.

Upvotes: 1

MAK
MAK

Reputation: 26586

This equivalent to 

for(int i=lo+r;i<(hi-r);i+=step)

in C (or C++, Java, C#, etc.)

(Note: this will only work if step is positive. If step is negative - i.e. lo+r>hi-r, you need change the check to i>(hi-r))

What it does is start a counter at lo+r, move it by step units until the counter equals or steps past hi-r.

Upvotes: 3

Mark Byers
Mark Byers

Reputation: 839234

Its a loop from lo + r (inclusive) to hi -r (exclusive) in increments of step.

Assuming step is positive, in C-like languages it could be written as:

 for (i = lo + r; i < hi - r; i += step) { ... }

Another way to write it in Python:

 i = lo + r
 while i < hi - r:
      # loop body
      i += step

If step is negative, the < becomes > in the above code.

Upvotes: 0

paxdiablo
paxdiablo

Reputation: 882756

You can read that as the following pseudo-code (for positive steps):

i = lo + r
while i < hi - r:
    # body of loop
    i = i + step

For negative steps:

i = lo + r
while i > hi - r:
    # body of loop
    i = i + step

In other words, it iterates the i variable from the first value, until it reaches or passes the second value, adjusting it by the third value each time through the loop.

Upvotes: 0

Eric O. Lebigot
Eric O. Lebigot

Reputation: 94605

Line

for i in range(lo + r, hi - r, step):

is a for loop with i running from lo+r to hi-r not included, by steps of step. Here is an example:

>>> for i in range(10, 31, 3):
...     print i
...     
10
13
16
19
22
25
28

Note that in range(start, end, step), the start and end values can be ordered in any way and that step can be positive or negative. This makes writing a C version a little cumbersome.

Thus, once you know Python, for i in range(lo + r, hi - r, step is the pseudo-code: in fact,

  • it is arguably more concise and legible than a while loop with counter initialization, test and increment on three different lines;
  • it nicely handles all the cases covered by Python (ordering of the start and end, and sign of the step).

Upvotes: 1

Related Questions