Александр Дубровский
2019-Dec-14 20:37 UTC
[R] 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]]
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, ????????? ?????????? <dubrovvsskkyy at gmail.com> 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]] > > ______________________________________________ > 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.
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 <boris.steipe at utoronto.ca> 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, ????????? ?????????? <dubrovvsskkyy at gmail.com> 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]] > > > > ______________________________________________ > > 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.
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, ????????? ?????????? <dubrovvsskkyy at gmail.com> 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]] > > ______________________________________________ > 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.