R help - Dec 2019 - Please help translate this program in python to R.

# Iterative Merge sort (Bottom Up)

# Iterative mergesort function to
# sort arr[0...n-1]
def mergeSort(a):

    current_size = 1

    # Outer loop for traversing Each
    # sub array of current_size
    while current_size < len(a) - 1:

        left = 0
        # Inner loop for merge call
        # in a sub array
        # Each complete Iteration sorts
        # the iterating sub array
        while left < len(a)-1:

            # mid index = left index of
            # sub array + current sub
            # array size - 1
            mid = left + current_size - 1

            # (False result,True result)
            # [Condition] Can use current_size
            # if 2 * current_size < len(a)-1
            # else len(a)-1
            right = ((2 * current_size + left - 1,
                    len(a) - 1)[2 * current_size
                          + left - 1 > len(a)-1])

            # Merge call for each sub array
            merge(a, left, mid, right)
            left = left + current_size*2

        # Increasing sub array size by
        # multiple of 2
        current_size = 2 * current_size

# Merge Function
def merge(a, l, m, r):
    n1 = m - l + 1
    n2 = r - m
    L = [0] * n1
    R = [0] * n2
    for i in range(0, n1):
        L[i] = a[l + i]
    for i in range(0, n2):
        R[i] = a[m + i + 1]

    i, j, k = 0, 0, l
    while i < n1 and j < n2:
        if L[i] > R[j]:
            a[k] = R[j]
            j += 1
        else:
            a[k] = L[i]
            i += 1
        k += 1

    while i < n1:
        a[k] = L[i]
        i += 1
        k += 1

    while j < n2:
        a[k] = R[j]
        j += 1
        k += 1


# Driver code
a = [12, 11, 13, 5, 6, 7]
print("Given array is ")
print(a)

mergeSort(a)

print("Sorted array is ")
print(a)

# Contributed by Madhur Chhangani [RCOEM]

	[[alternative HTML version deleted]]

See my response to the C++ question you posted a minute later.

B.



> On 2019-12-15, at 05:35, ????????? ?????????? <dubrovvsskkyy at
gmail.com> wrote:
> 
> # Iterative Merge sort (Bottom Up)
> 
> # Iterative mergesort function to
> # sort arr[0...n-1]
> def mergeSort(a):
> 
>    current_size = 1
> 
>    # Outer loop for traversing Each
>    # sub array of current_size
>    while current_size < len(a) - 1:
> 
>        left = 0
>        # Inner loop for merge call
>        # in a sub array
>        # Each complete Iteration sorts
>        # the iterating sub array
>        while left < len(a)-1:
> 
>            # mid index = left index of
>            # sub array + current sub
>            # array size - 1
>            mid = left + current_size - 1
> 
>            # (False result,True result)
>            # [Condition] Can use current_size
>            # if 2 * current_size < len(a)-1
>            # else len(a)-1
>            right = ((2 * current_size + left - 1,
>                    len(a) - 1)[2 * current_size
>                          + left - 1 > len(a)-1])
> 
>            # Merge call for each sub array
>            merge(a, left, mid, right)
>            left = left + current_size*2
> 
>        # Increasing sub array size by
>        # multiple of 2
>        current_size = 2 * current_size
> 
> # Merge Function
> def merge(a, l, m, r):
>    n1 = m - l + 1
>    n2 = r - m
>    L = [0] * n1
>    R = [0] * n2
>    for i in range(0, n1):
>        L[i] = a[l + i]
>    for i in range(0, n2):
>        R[i] = a[m + i + 1]
> 
>    i, j, k = 0, 0, l
>    while i < n1 and j < n2:
>        if L[i] > R[j]:
>            a[k] = R[j]
>            j += 1
>        else:
>            a[k] = L[i]
>            i += 1
>        k += 1
> 
>    while i < n1:
>        a[k] = L[i]
>        i += 1
>        k += 1
> 
>    while j < n2:
>        a[k] = R[j]
>        j += 1
>        k += 1
> 
> 
> # Driver code
> a = [12, 11, 13, 5, 6, 7]
> print("Given array is ")
> print(a)
> 
> mergeSort(a)
> 
> print("Sorted array is ")
> print(a)
> 
> # Contributed by Madhur Chhangani [RCOEM]
> 
> 	[[alternative HTML version deleted]]
> 
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

And similar to my response to the C++ question you posted, it is
possible to incorporate Python code into R programs using the
reticulate package.

On Sun, Dec 15, 2019 at 5:58 AM Boris Steipe <boris.steipe at utoronto.ca>
wrote:
>
> See my response to the C++ question you posted a minute later.
>
> B.
>
>
>
>
> > On 2019-12-15, at 05:35, ????????? ?????????? <dubrovvsskkyy at
gmail.com> wrote:
> >
> > # Iterative Merge sort (Bottom Up)
> >
> > # Iterative mergesort function to
> > # sort arr[0...n-1]
> > def mergeSort(a):
> >
> >    current_size = 1
> >
> >    # Outer loop for traversing Each
> >    # sub array of current_size
> >    while current_size < len(a) - 1:
> >
> >        left = 0
> >        # Inner loop for merge call
> >        # in a sub array
> >        # Each complete Iteration sorts
> >        # the iterating sub array
> >        while left < len(a)-1:
> >
> >            # mid index = left index of
> >            # sub array + current sub
> >            # array size - 1
> >            mid = left + current_size - 1
> >
> >            # (False result,True result)
> >            # [Condition] Can use current_size
> >            # if 2 * current_size < len(a)-1
> >            # else len(a)-1
> >            right = ((2 * current_size + left - 1,
> >                    len(a) - 1)[2 * current_size
> >                          + left - 1 > len(a)-1])
> >
> >            # Merge call for each sub array
> >            merge(a, left, mid, right)
> >            left = left + current_size*2
> >
> >        # Increasing sub array size by
> >        # multiple of 2
> >        current_size = 2 * current_size
> >
> > # Merge Function
> > def merge(a, l, m, r):
> >    n1 = m - l + 1
> >    n2 = r - m
> >    L = [0] * n1
> >    R = [0] * n2
> >    for i in range(0, n1):
> >        L[i] = a[l + i]
> >    for i in range(0, n2):
> >        R[i] = a[m + i + 1]
> >
> >    i, j, k = 0, 0, l
> >    while i < n1 and j < n2:
> >        if L[i] > R[j]:
> >            a[k] = R[j]
> >            j += 1
> >        else:
> >            a[k] = L[i]
> >            i += 1
> >        k += 1
> >
> >    while i < n1:
> >        a[k] = L[i]
> >        i += 1
> >        k += 1
> >
> >    while j < n2:
> >        a[k] = R[j]
> >        j += 1
> >        k += 1
> >
> >
> > # Driver code
> > a = [12, 11, 13, 5, 6, 7]
> > print("Given array is ")
> > print(a)
> >
> > mergeSort(a)
> >
> > print("Sorted array is ")
> > print(a)
> >
> > # Contributed by Madhur Chhangani [RCOEM]
> >
> >       [[alternative HTML version deleted]]
> >
> > ______________________________________________
> > R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> > https://stat.ethz.ch/mailman/listinfo/r-help
> > PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> > and provide commented, minimal, self-contained, reproducible code.
>
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.

The obvious question is "why?"
If you just want to sort stuff, ?sort and ?order tell you about the
sorting methods available in R.
If you want to translate this specific algorithm into R for some reason,
(a) if you don't know enough about array processing in R to do this
yourself,
     how are you going to know enough to *use* it?
(b) There is a fundamental difference between arrays in Python and R which
     means that the algorithm as presented cannot possibly work in R.

Here's the difference.
>>> def f(x): x[1] = 5
...
>>> a = [1,2,3]
>>> f(a)
>>> a
[1, 5, 3]

Arrays in Python are collections of *variables* and if you pass one to
a function,
the function can *change* the very same array that you passed in.
> f <- function (x) x[2] <- 5
> a <- c(1,2,3)
> f(a)
> a
[1] 1 2 3

This is a completely different result.
Arrays in R are collections of *values*.  R acts *as if*
  x[i] <- e
really meant
  x <- get("[<-")(x, i, e)
computing a whole new array and assigning it to x.
There is in fact an actual function that does this update,
and get("[<-") returns it.
I said "as if", because there are things you can do to make the actual
implementation much more efficient, but the *observable behaviour*
is as if the entire array were replaced.
Note that this has nothing to do with how the two languages pass
arguments to functions,
it's about what an array *is* and how you work with them.

The bottom line is that if you *could* translate this algorithm from
Python to R,
you *shouldn't*.

















321

On Sun, 15 Dec 2019 at 14:56, ????????? ??????????
<dubrovvsskkyy at gmail.com> wrote:
>
> # Iterative Merge sort (Bottom Up)
>
> # Iterative mergesort function to
> # sort arr[0...n-1]
> def mergeSort(a):
>
>     current_size = 1
>
>     # Outer loop for traversing Each
>     # sub array of current_size
>     while current_size < len(a) - 1:
>
>         left = 0
>         # Inner loop for merge call
>         # in a sub array
>         # Each complete Iteration sorts
>         # the iterating sub array
>         while left < len(a)-1:
>
>             # mid index = left index of
>             # sub array + current sub
>             # array size - 1
>             mid = left + current_size - 1
>
>             # (False result,True result)
>             # [Condition] Can use current_size
>             # if 2 * current_size < len(a)-1
>             # else len(a)-1
>             right = ((2 * current_size + left - 1,
>                     len(a) - 1)[2 * current_size
>                           + left - 1 > len(a)-1])
>
>             # Merge call for each sub array
>             merge(a, left, mid, right)
>             left = left + current_size*2
>
>         # Increasing sub array size by
>         # multiple of 2
>         current_size = 2 * current_size
>
> # Merge Function
> def merge(a, l, m, r):
>     n1 = m - l + 1
>     n2 = r - m
>     L = [0] * n1
>     R = [0] * n2
>     for i in range(0, n1):
>         L[i] = a[l + i]
>     for i in range(0, n2):
>         R[i] = a[m + i + 1]
>
>     i, j, k = 0, 0, l
>     while i < n1 and j < n2:
>         if L[i] > R[j]:
>             a[k] = R[j]
>             j += 1
>         else:
>             a[k] = L[i]
>             i += 1
>         k += 1
>
>     while i < n1:
>         a[k] = L[i]
>         i += 1
>         k += 1
>
>     while j < n2:
>         a[k] = R[j]
>         j += 1
>         k += 1
>
>
> # Driver code
> a = [12, 11, 13, 5, 6, 7]
> print("Given array is ")
> print(a)
>
> mergeSort(a)
>
> print("Sorted array is ")
> print(a)
>
> # Contributed by Madhur Chhangani [RCOEM]
>
>         [[alternative HTML version deleted]]
>
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide
http://www.R-project.org/posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.