Please help translate this program in C++ to R

classic Classic list List threaded Threaded
4 messages Options
Reply | Threaded
Open this post in threaded view
|

Please help translate this program in C++ to R

Александр Дубровский
/* Iterative C program for merge sort */
#include<stdlib.h>
#include<stdio.h>

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
*/
void merge(int arr[], int l, int m, int r);

// Utility function to find minimum of two integers
int min(int x, int y) { return (x<y)? x :y; }


/* Iterative mergesort function to sort arr[0...n-1] */
void mergeSort(int arr[], int n)
{
   int curr_size;  // For current size of subarrays to be merged
                   // curr_size varies from 1 to n/2
   int left_start; // For picking starting index of left subarray
                   // to be merged

   // Merge subarrays in bottom up manner.  First merge subarrays of
   // size 1 to create sorted subarrays of size 2, then merge subarrays
   // of size 2 to create sorted subarrays of size 4, and so on.
   for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
   {
       // Pick starting point of different subarrays of current size
       for (left_start=0; left_start<n-1; left_start += 2*curr_size)
       {
           // Find ending point of left subarray. mid+1 is starting
           // point of right
           int mid = min(left_start + curr_size - 1, n-1);

           int right_end = min(left_start + 2*curr_size - 1, n-1);

           // Merge Subarrays arr[left_start...mid] &
arr[mid+1...right_end]
           merge(arr, left_start, mid, right_end);
       }
   }
}

/* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
*/
void merge(int arr[], int l, int m, int r)
{
    int i, j, k;
    int n1 = m - l + 1;
    int n2 =  r - m;

    /* create temp arrays */
    int L[n1], R[n2];

    /* Copy data to temp arrays L[] and R[] */
    for (i = 0; i < n1; i++)
        L[i] = arr[l + i];
    for (j = 0; j < n2; j++)
        R[j] = arr[m + 1+ j];

    /* Merge the temp arrays back into arr[l..r]*/
    i = 0;
    j = 0;
    k = l;
    while (i < n1 && j < n2)
    {
        if (L[i] <= R[j])
        {
            arr[k] = L[i];
            i++;
        }
        else
        {
            arr[k] = R[j];
            j++;
        }
        k++;
    }

    /* Copy the remaining elements of L[], if there are any */
    while (i < n1)
    {
        arr[k] = L[i];
        i++;
        k++;
    }

    /* Copy the remaining elements of R[], if there are any */
    while (j < n2)
    {
        arr[k] = R[j];
        j++;
        k++;
    }
}

/* Function to print an array */
void printArray(int A[], int size)
{
    int i;
    for (i=0; i < size; i++)
        printf("%d ", A[i]);
    printf("\n");
}

/* Driver program to test above functions */
int main()
{
    int arr[] = {12, 11, 13, 5, 6, 7};
    int n = sizeof(arr)/sizeof(arr[0]);

    printf("Given array is \n");
    printArray(arr, n);

    mergeSort(arr, n);

    printf("\nSorted array is \n");
    printArray(arr, n);
    return 0;
}

        [[alternative HTML version deleted]]

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Please help translate this program in C++ to R

Boris Steipe
See this thread why that's a bad idea ...
 https://stackoverflow.com/questions/26080716/merge-sort-in-r

... and use the code given there, or give us some context why a literal translation would be important to you.

Cheers,
Boris




> On 2019-12-15, at 05:37, Александр Дубровский <[hidden email]> wrote:
>
> /* Iterative C program for merge sort */
> #include<stdlib.h>
> #include<stdio.h>
>
> /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
> */
> void merge(int arr[], int l, int m, int r);
>
> // Utility function to find minimum of two integers
> int min(int x, int y) { return (x<y)? x :y; }
>
>
> /* Iterative mergesort function to sort arr[0...n-1] */
> void mergeSort(int arr[], int n)
> {
>   int curr_size;  // For current size of subarrays to be merged
>                   // curr_size varies from 1 to n/2
>   int left_start; // For picking starting index of left subarray
>                   // to be merged
>
>   // Merge subarrays in bottom up manner.  First merge subarrays of
>   // size 1 to create sorted subarrays of size 2, then merge subarrays
>   // of size 2 to create sorted subarrays of size 4, and so on.
>   for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
>   {
>       // Pick starting point of different subarrays of current size
>       for (left_start=0; left_start<n-1; left_start += 2*curr_size)
>       {
>           // Find ending point of left subarray. mid+1 is starting
>           // point of right
>           int mid = min(left_start + curr_size - 1, n-1);
>
>           int right_end = min(left_start + 2*curr_size - 1, n-1);
>
>           // Merge Subarrays arr[left_start...mid] &
> arr[mid+1...right_end]
>           merge(arr, left_start, mid, right_end);
>       }
>   }
> }
>
> /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
> */
> void merge(int arr[], int l, int m, int r)
> {
>    int i, j, k;
>    int n1 = m - l + 1;
>    int n2 =  r - m;
>
>    /* create temp arrays */
>    int L[n1], R[n2];
>
>    /* Copy data to temp arrays L[] and R[] */
>    for (i = 0; i < n1; i++)
>        L[i] = arr[l + i];
>    for (j = 0; j < n2; j++)
>        R[j] = arr[m + 1+ j];
>
>    /* Merge the temp arrays back into arr[l..r]*/
>    i = 0;
>    j = 0;
>    k = l;
>    while (i < n1 && j < n2)
>    {
>        if (L[i] <= R[j])
>        {
>            arr[k] = L[i];
>            i++;
>        }
>        else
>        {
>            arr[k] = R[j];
>            j++;
>        }
>        k++;
>    }
>
>    /* Copy the remaining elements of L[], if there are any */
>    while (i < n1)
>    {
>        arr[k] = L[i];
>        i++;
>        k++;
>    }
>
>    /* Copy the remaining elements of R[], if there are any */
>    while (j < n2)
>    {
>        arr[k] = R[j];
>        j++;
>        k++;
>    }
> }
>
> /* Function to print an array */
> void printArray(int A[], int size)
> {
>    int i;
>    for (i=0; i < size; i++)
>        printf("%d ", A[i]);
>    printf("\n");
> }
>
> /* Driver program to test above functions */
> int main()
> {
>    int arr[] = {12, 11, 13, 5, 6, 7};
>    int n = sizeof(arr)/sizeof(arr[0]);
>
>    printf("Given array is \n");
>    printArray(arr, n);
>
>    mergeSort(arr, n);
>
>    printf("\nSorted array is \n");
>    printArray(arr, n);
>    return 0;
> }
>
> [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] 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.

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Please help translate this program in C++ to R

Eric Berger
It is fairly easy to incorporate C++ code into R programs using the
Rcpp package.
Definitely worth the effort to learn how to do this.

On Sun, Dec 15, 2019 at 5:48 AM Boris Steipe <[hidden email]> wrote:

>
> See this thread why that's a bad idea ...
>  https://stackoverflow.com/questions/26080716/merge-sort-in-r
>
> ... and use the code given there, or give us some context why a literal translation would be important to you.
>
> Cheers,
> Boris
>
>
>
>
> > On 2019-12-15, at 05:37, Александр Дубровский <[hidden email]> wrote:
> >
> > /* Iterative C program for merge sort */
> > #include<stdlib.h>
> > #include<stdio.h>
> >
> > /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
> > */
> > void merge(int arr[], int l, int m, int r);
> >
> > // Utility function to find minimum of two integers
> > int min(int x, int y) { return (x<y)? x :y; }
> >
> >
> > /* Iterative mergesort function to sort arr[0...n-1] */
> > void mergeSort(int arr[], int n)
> > {
> >   int curr_size;  // For current size of subarrays to be merged
> >                   // curr_size varies from 1 to n/2
> >   int left_start; // For picking starting index of left subarray
> >                   // to be merged
> >
> >   // Merge subarrays in bottom up manner.  First merge subarrays of
> >   // size 1 to create sorted subarrays of size 2, then merge subarrays
> >   // of size 2 to create sorted subarrays of size 4, and so on.
> >   for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
> >   {
> >       // Pick starting point of different subarrays of current size
> >       for (left_start=0; left_start<n-1; left_start += 2*curr_size)
> >       {
> >           // Find ending point of left subarray. mid+1 is starting
> >           // point of right
> >           int mid = min(left_start + curr_size - 1, n-1);
> >
> >           int right_end = min(left_start + 2*curr_size - 1, n-1);
> >
> >           // Merge Subarrays arr[left_start...mid] &
> > arr[mid+1...right_end]
> >           merge(arr, left_start, mid, right_end);
> >       }
> >   }
> > }
> >
> > /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
> > */
> > void merge(int arr[], int l, int m, int r)
> > {
> >    int i, j, k;
> >    int n1 = m - l + 1;
> >    int n2 =  r - m;
> >
> >    /* create temp arrays */
> >    int L[n1], R[n2];
> >
> >    /* Copy data to temp arrays L[] and R[] */
> >    for (i = 0; i < n1; i++)
> >        L[i] = arr[l + i];
> >    for (j = 0; j < n2; j++)
> >        R[j] = arr[m + 1+ j];
> >
> >    /* Merge the temp arrays back into arr[l..r]*/
> >    i = 0;
> >    j = 0;
> >    k = l;
> >    while (i < n1 && j < n2)
> >    {
> >        if (L[i] <= R[j])
> >        {
> >            arr[k] = L[i];
> >            i++;
> >        }
> >        else
> >        {
> >            arr[k] = R[j];
> >            j++;
> >        }
> >        k++;
> >    }
> >
> >    /* Copy the remaining elements of L[], if there are any */
> >    while (i < n1)
> >    {
> >        arr[k] = L[i];
> >        i++;
> >        k++;
> >    }
> >
> >    /* Copy the remaining elements of R[], if there are any */
> >    while (j < n2)
> >    {
> >        arr[k] = R[j];
> >        j++;
> >        k++;
> >    }
> > }
> >
> > /* Function to print an array */
> > void printArray(int A[], int size)
> > {
> >    int i;
> >    for (i=0; i < size; i++)
> >        printf("%d ", A[i]);
> >    printf("\n");
> > }
> >
> > /* Driver program to test above functions */
> > int main()
> > {
> >    int arr[] = {12, 11, 13, 5, 6, 7};
> >    int n = sizeof(arr)/sizeof(arr[0]);
> >
> >    printf("Given array is \n");
> >    printArray(arr, n);
> >
> >    mergeSort(arr, n);
> >
> >    printf("\nSorted array is \n");
> >    printArray(arr, n);
> >    return 0;
> > }
> >
> >       [[alternative HTML version deleted]]
> >
> > ______________________________________________
> > [hidden email] 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.
>
> ______________________________________________
> [hidden email] 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.

______________________________________________
[hidden email] 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.
Reply | Threaded
Open this post in threaded view
|

Re: Please help translate this program in C++ to R

Richard O'Keefe-2
In reply to this post by Александр Дубровский
As a C implementation of merge sort, that is the very reverse of impressive.
I would not translate *that* code into anything.
There is a fundamental difference between between arrays in C and arrays in R,
and it is the same as the difference between Python and R.

You are MUCH better to start from high level pseudocode and express that in R
than to start from code tangled up with the presuppositions and peculiarities of
another language with quite different presuppositions and peculiarities.


On Sun, 15 Dec 2019 at 14:57, Александр Дубровский
<[hidden email]> wrote:

>
> /* Iterative C program for merge sort */
> #include<stdlib.h>
> #include<stdio.h>
>
> /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
> */
> void merge(int arr[], int l, int m, int r);
>
> // Utility function to find minimum of two integers
> int min(int x, int y) { return (x<y)? x :y; }
>
>
> /* Iterative mergesort function to sort arr[0...n-1] */
> void mergeSort(int arr[], int n)
> {
>    int curr_size;  // For current size of subarrays to be merged
>                    // curr_size varies from 1 to n/2
>    int left_start; // For picking starting index of left subarray
>                    // to be merged
>
>    // Merge subarrays in bottom up manner.  First merge subarrays of
>    // size 1 to create sorted subarrays of size 2, then merge subarrays
>    // of size 2 to create sorted subarrays of size 4, and so on.
>    for (curr_size=1; curr_size<=n-1; curr_size = 2*curr_size)
>    {
>        // Pick starting point of different subarrays of current size
>        for (left_start=0; left_start<n-1; left_start += 2*curr_size)
>        {
>            // Find ending point of left subarray. mid+1 is starting
>            // point of right
>            int mid = min(left_start + curr_size - 1, n-1);
>
>            int right_end = min(left_start + 2*curr_size - 1, n-1);
>
>            // Merge Subarrays arr[left_start...mid] &
> arr[mid+1...right_end]
>            merge(arr, left_start, mid, right_end);
>        }
>    }
> }
>
> /* Function to merge the two haves arr[l..m] and arr[m+1..r] of array arr[]
> */
> void merge(int arr[], int l, int m, int r)
> {
>     int i, j, k;
>     int n1 = m - l + 1;
>     int n2 =  r - m;
>
>     /* create temp arrays */
>     int L[n1], R[n2];
>
>     /* Copy data to temp arrays L[] and R[] */
>     for (i = 0; i < n1; i++)
>         L[i] = arr[l + i];
>     for (j = 0; j < n2; j++)
>         R[j] = arr[m + 1+ j];
>
>     /* Merge the temp arrays back into arr[l..r]*/
>     i = 0;
>     j = 0;
>     k = l;
>     while (i < n1 && j < n2)
>     {
>         if (L[i] <= R[j])
>         {
>             arr[k] = L[i];
>             i++;
>         }
>         else
>         {
>             arr[k] = R[j];
>             j++;
>         }
>         k++;
>     }
>
>     /* Copy the remaining elements of L[], if there are any */
>     while (i < n1)
>     {
>         arr[k] = L[i];
>         i++;
>         k++;
>     }
>
>     /* Copy the remaining elements of R[], if there are any */
>     while (j < n2)
>     {
>         arr[k] = R[j];
>         j++;
>         k++;
>     }
> }
>
> /* Function to print an array */
> void printArray(int A[], int size)
> {
>     int i;
>     for (i=0; i < size; i++)
>         printf("%d ", A[i]);
>     printf("\n");
> }
>
> /* Driver program to test above functions */
> int main()
> {
>     int arr[] = {12, 11, 13, 5, 6, 7};
>     int n = sizeof(arr)/sizeof(arr[0]);
>
>     printf("Given array is \n");
>     printArray(arr, n);
>
>     mergeSort(arr, n);
>
>     printf("\nSorted array is \n");
>     printArray(arr, n);
>     return 0;
> }
>
>         [[alternative HTML version deleted]]
>
> ______________________________________________
> [hidden email] 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.

______________________________________________
[hidden email] 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.