2

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++?

Improve this question

5 Answers 5

Reset to default
3

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

What you have is very dangerous, could loop forever. I don't believe it's equivalent to the python range.
@Mat: True. It may loop forever, but I can't think of a way that works for both positive and negative step in C-like languages. I am updating my answer to work only for the positive case.
@MAK, you fixed your code but not the description in the final paragraph.
1

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).
Improve this answer

Comments

1

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

0

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.

Improve this answer

Comments

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.