- **C Programming**
(*http://www.velocityreviews.com/forums/f42-c-programming.html*)

- - **merge sort**
(*http://www.velocityreviews.com/forums/t564264-merge-sort.html*)

merge sortI have a little problem with implementing a recursive merge sort
I have to use a function mergesort that takes 3 arguments - an array, its size, and an help array(i.e mergesort(int [] array, int size, int[] temp] . I have to use only the temp array for the sorting, I cant use two help arrays for the sorting, and I cant change the signature of the function. also have a merge function that takes 5 arguments - left array and its size, right array and its size, and final array. I dont have a problem with the merge function only with the mergesort. can someone post the code for it? |

Re: merge sortmooon33358@gmail.com said:
> I have a little problem with implementing a recursive merge sort > I have to use a function mergesort that takes 3 arguments - an array, > its size, and an help array(i.e mergesort(int [] array, int size, > int[] temp] . That ain't ever gonna compile. > I have to use only the temp array for the sorting, I > cant use two help arrays for the sorting, and I cant change the > signature of the function. > also have a merge function that takes 5 arguments - left array and its > size, right array and its size, and final array. > I dont have a problem with the merge function only with the mergesort. > can someone post the code for it? "Merging (or collating) means the combination of two or more ordered files into a single ordered file." (Knuth) (For "file", we can read "array" if we prefer.) This is indeed the easy part, and I will presume that you have no problem with it. The difficult bit is getting the two ordered arrays in the first place! But this turns out not to be so hard. To mergesort an array, simply split your unordered array into two parts, and mergesort them both (unless of course they are already in order), and then merge them (which you say you already know how to do). -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ Google users: <http://www.cpax.org.uk/prg/writings/googly.php> "Usenet is a strange place" - dmr 29 July 1999 |

Re: merge sortOn Dec 28, 10:59*am, Richard Heathfield <r...@see.sig.invalid> wrote:
> mooon33...@gmail.com said: > > > I have a little problem with implementing a recursive merge sort > > I have to use a function mergesort that takes 3 arguments - an array, > > its size, and an help array(i.e mergesort(int [] array, int size, > > int[] temp] . > > That ain't ever gonna compile. > > > I have to use only the temp array for the sorting, I > > cant use two help arrays for the sorting, and I cant change the > > signature of the function. > > also have a merge function that takes 5 arguments - left array and its > > size, right array and its size, and final array. > > I dont have a problem with the merge function only with the mergesort. > > can someone post the code for it? > > "Merging (or collating) means the combination of two or more ordered files > into a single ordered file." (Knuth) > > (For "file", we can read "array" if we prefer.) > > This is indeed the easy part, and I will presume that you have no problem > with it. The difficult bit is getting the two ordered arrays in the first > place! > > But this turns out not to be so hard. To mergesort an array, simply split > your unordered array into two parts, and mergesort them both (unless of > course they are already in order), and then merge them (which you say you > already know how to do). > > -- > Richard Heathfield <http://www.cpax.org.uk> > Email: -http://www. +rjh@ > Google users: <http://www.cpax.org.uk/prg/writings/googly.php> > "Usenet is a strange place" - dmr 29 July 1999 why do you think it won't compile? thats the exercise and can you post a sample from the code of my mergesort? |

Re: merge sortmooon33358@gmail.com said:
> On Dec 28, 10:59 am, Richard Heathfield <r...@see.sig.invalid> wrote: >> mooon33...@gmail.com said: >> >> > I have a little problem with implementing a recursive merge sort >> > I have to use a function mergesort that takes 3 arguments - an array, >> > its size, and an help array(i.e mergesort(int [] array, int size, >> > int[] temp] . >> >> That ain't ever gonna compile. >> <snip> > > why do you think it won't compile? thats the exercise Partly because int [] array isn't a legal description of a parameter to a function, and partly because ] isn't a legal way to close a function parameter list. You probably meant to write: int mergesort(int array[], int size, int temp[]) > and can you post a sample from the code of my mergesort? I'd be delighted to post a sample from your mergesort code, if you'd be so good as to tell me where you have placed it and how I can gain access to that place. -- Richard Heathfield <http://www.cpax.org.uk> Email: -http://www. +rjh@ Google users: <http://www.cpax.org.uk/prg/writings/googly.php> "Usenet is a strange place" - dmr 29 July 1999 |

Re: merge sortOn Dec 28, 12:16*am, mooon33...@gmail.com wrote:
> I have a little problem with implementing a recursive merge sort > I have to use a function mergesort that takes 3 arguments - an array, > its size, and an help array(i.e mergesort(int [] array, int size, > int[] temp] . I have to use only the temp array for the sorting, I > cant use two help arrays for the sorting, and I cant change the > signature of the function. > also have a merge function that takes 5 arguments - left array and its > size, right array and its size, and final array. > I dont have a problem with the merge function only with the mergesort. > can someone post the code for it? Post your attempt in news:comp.programming and some of the regulars will tell you where you went off. Follow-ups set. |

Re: merge sortOn Dec 28, 12:16*am, mooon33...@gmail.com wrote:
> I have a little problem with implementing a recursive merge sort > I have to use a function mergesort that takes 3 arguments - an array, > its size, and an help array(i.e mergesort(int [] array, int size, > int[] temp] . I have to use only the temp array for the sorting, I > cant use two help arrays for the sorting, and I cant change the > signature of the function. > also have a merge function that takes 5 arguments - left array and its > size, right array and its size, and final array. > I dont have a problem with the merge function only with the mergesort. > can someone post the code for it? Why are we merging? Any in-place sort will do without the use of the help array. And there are other out-of-place sort routines that can use the help array. |

Re: merge sortmooon33358@gmail.com wrote:
> > I have a little problem with implementing a recursive merge sort > I have to use a function mergesort that takes 3 arguments - an > array, its size, and an help array(i.e mergesort(int [] array, int > size, int[] temp] . I have to use only the temp array for the > sorting, I cant use two help arrays for the sorting, and I cant > change the signature of the function. also have a merge function > that takes 5 arguments - left array and its size, right array and > its size, and final array. I dont have a problem with the merge > function only with the mergesort. can someone post the code for it? If the array is not essential, see about making the sorted item a singly linked list. For such, there is adequate mergesort code in the demonstration uses for hashlib. Lists are intrinsically unlimited (apart from machine resources) as to size. Mergesort uses minimal extra storage. See: <http://cbfalconer.home.att.net/download/> (for hashlib) -- Merry Christmas, Happy Hanukah, Happy New Year Joyeux Noel, Bonne Annee, Frohe Weihnachten Chuck F (cbfalconer at maineline dot net) <http://cbfalconer.home.att.net> -- Posted via a free Usenet account from http://www.teranews.com |

Re: merge sorthere is my code
my problem is the mergesort function what I need to write there? #include <stdio.h> #include <stdlib.h> void merge(int *leftArr, int leftSize, int *rightArr, int rightSize, int *sortArr); void mergeSort( int *Array, int n, int *temp ); int main() { int n , Array[100] , temp[100] ; int i ; scanf("%d", &n); if( ( n <= 0 ) || ( n > 100 ) ) { printf("error!\n"); return -1; } for( i = 0; i < n; i++ ) { scanf("%d", &Array[i]); } mergeSort( Array, n, temp ); for(i=0;i<n;i++) { printf("%d ",Array[i]); } printf("\n"); return 0; } void mergeSort( int *Array, int n, int *temp ) { int leftArr[100] = {0}, rightArr[100] = {0}, rightSize,leftSize,temp_Size; int i,j,temp_int; if (n < 2) return; for (i=0; i<n; i++) temp[i] = Array[i]; for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (temp[i] > temp[j]) { /*swap:*/ temp_int = temp[i]; temp[i] = temp[j]; temp[j] = temp_int; } /* end of if */ leftSize = n/2; rightSize = n - leftSize; mergeSort( leftArr, leftSize, temp ); temp_Size = leftSize; for( i = 0; i < leftSize; i++ ) leftArr[i] = Array[i]; for( i = 0; i < temp_Size; i++ ) { temp[i] = Array[i]; } for( i = 0; i < temp_Size; i++ ) { leftArr[i] = temp[i]; } temp_Size = rightSize; for( i = 0; i < temp_Size; i++ ) { temp[i] = Array[leftSize+i]; } for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) if (temp[i] > temp[j]) { /*swap:*/ temp_int = temp[i]; temp[i] = temp[j]; temp[j] = temp_int; } /* end of if */ mergeSort( rightArr, rightArr, temp ); for( i = 0; i < temp_Size; i++ ) rightArr[i] = temp[i]; mergeSort( rightArr, rightSize, temp ); merge( leftArr, leftSize, rightArr, rightSize, Array ); } /* This function merges both sub arrays */ void merge(int *leftArr, int leftSize, int *rightArr, int rightSize, int *sortArr) { int i =0, j = 0, k = 0; while ( ( i < leftSize )&& ( j < rightSize ) ) { if ( leftArr[i] < rightArr[j] ) { sortArr[k] = leftArr[i]; i++; k++; } else { sortArr[k] = rightArr[j]; j++; k++; } } while(i<leftSize) { sortArr[k]= leftArr[i]; i++; k++; } while(j<rightSize) { sortArr[k]= rightArr[j]; j++; k++; } } |

Re: merge sortOn Dec 28, 2:22*pm, mooon33...@gmail.com wrote:
> here is my code > my problem is the mergesort function > what I need to write there? > > #include <stdio.h> > #include <stdlib.h> > > void merge(int *leftArr, int leftSize, int *rightArr, int rightSize, > int *sortArr); > void mergeSort( int *Array, int n, int *temp ); > > int main() > { > * * * * int n , Array[100] , temp[100] ; > * * * * int i ; > > * * * * scanf("%d", &n); > > * * * * if( ( n <= 0 ) || *( n > 100 ) ) > * * * * { > * * * * * * * * printf("error!\n"); > * * * * * * * * return -1; > * * * * } > * * * * for( i = 0; i < n; i++ ) > * * * * { > * * * * * * * * scanf("%d", &Array[i]); > * * * * } > > * * * * mergeSort( Array, n, temp ); > * * * * for(i=0;i<n;i++) > * * * * { > * * * * * * * * printf("%d ",Array[i]); > * * * * } > * * * * printf("\n"); > > return 0; > > } > > void mergeSort( int *Array, int n, int *temp ) > { > * * * * int *leftArr[100] = {0}, rightArr[100] = {0}, > rightSize,leftSize,temp_Size; > * * * * int i,j,temp_int; > > * * * * if (n < 2) > * * * * * * * * return; > > * * * * for (i=0; i<n; i++) temp[i] = Array[i]; > * * * * for (i=0; i<n-1; i++) > * * * * * * * * for (j=i+1; j<n; j++) > * * * * * * * * * * * * if (temp[i] > temp[j]) { */*swap:*/ > * * * * * * * * * * * * * * * * temp_int = temp[i]; > * * * * * * * * * * * * * * * * temp[i] = temp[j]; > * * * * * * * * * * * * * * * * temp[j] = temp_int; > * * * * * * * * * * * * } /* end of if */ > > * * * * leftSize = n/2; > * * * * rightSize = *n - leftSize; > * * * * mergeSort( leftArr, leftSize, temp ); > > * * * * temp_Size = leftSize; > * * * * for( i = 0; i < leftSize; i++ ) > * * * * * * * * leftArr[i] = Array[i]; > > * * * * for( i = 0; i < temp_Size; i++ ) > * * * * { > * * * * * * * * temp[i] = Array[i]; > * * * * } > > * * * * for( i = 0; i < temp_Size; i++ ) > * * * * { > * * * * * * * * leftArr[i] = temp[i]; > * * * * } > > * * * * temp_Size = rightSize; > > * * * * for( i = 0; i < temp_Size; i++ ) > * * * * { > * * * * * * * * temp[i] = Array[leftSize+i]; > * * * * } > > * * * * for (i=0; i<n-1; i++) > * * * * * * * * for (j=i+1; j<n; j++) > * * * * * * * * * * * * if (temp[i] > temp[j]) { */*swap:*/ > * * * * * * * * * * * * * * * * temp_int = temp[i]; > * * * * * * * * * * * * * * * * temp[i] = temp[j]; > * * * * * * * * * * * * * * * * temp[j] = temp_int; > * * * * * * * * * * * * } /* end of if */ > > * * * * * * * * * * * * mergeSort( rightArr, rightArr, temp ); > * * * * for( i = 0; i < temp_Size; i++ ) > * * * * * * * * rightArr[i] = temp[i]; > > * * * * *mergeSort( rightArr, rightSize, temp ); > > * * * * merge( leftArr, leftSize, rightArr, rightSize, Array );} > > /* This function merges both sub arrays */ > > void merge(int *leftArr, int leftSize, int *rightArr, int rightSize, > int *sortArr) > { > * * * * int i =0, j = 0, k = 0; > > * * * * while ( ( i < leftSize )&& ( *j < rightSize ) ) > * * * * { > * * * * * * * * if ( leftArr[i] < rightArr[j] ) > * * * * * * * * { > * * * * * * * * * * * * sortArr[k] = leftArr[i]; > * * * * * * * * * * * * i++; > * * * * * * * * * * * * k++; > * * * * * * * * } > * * * * * * * * else > * * * * * * * * { > * * * * * * * * * * * * sortArr[k] = rightArr[j]; > * * * * * * * * * * * * j++; > * * * * * * * * * * * * k++; > * * * * * * * * } > > * * * * } > * * * * while(i<leftSize) > * * * * { > * * * * * * * * sortArr[k]= leftArr[i]; > * * * * * * * * i++; > * * * * * * * * k++; > * * * * } > * * * * while(j<rightSize) > * * * * { > * * * * * * * * sortArr[k]= rightArr[j]; > * * * * * * * * j++; > * * * * * * * * k++; > * * * * } > > > > } Your merge() is fine {if a bit verbose} but your mergesort is not even close. |

Re: merge sortmooon33358@gmail.com wrote:
> > I have a little problem with implementing a recursive merge sort > I have to use a function mergesort that takes 3 arguments - an array, > its size, and an help array(i.e mergesort(int [] array, int size, > int[] temp] . I have to use only the temp array for the sorting, I > cant use two help arrays for the sorting, and I cant change the > signature of the function. > also have a merge function that takes 5 arguments - left array and its > size, right array and its size, and final array. > I dont have a problem with the merge function only with the mergesort. > can someone post the code for it? /* BEGIN mergesort.c */ void mergesort(int array[], int size, int temp[]) { if (size > 1) { int *mid_ptr; int const half = size / 2; int *const after_buff = temp + half; int *const middle = array + half; int *const after_array = array + size; mergesort(middle, size - half, temp); mergesort(array, half, temp); do { if (*array > *middle) { mid_ptr = middle; temp = after_buff; do { *--temp = *--mid_ptr; } while (array != mid_ptr); mid_ptr = middle; *array++ = *mid_ptr++; while (middle != array) { *array++ = *(*temp > *mid_ptr ? mid_ptr++ : temp++); } while (after_buff != temp) { if (after_array != mid_ptr) { *array++ = *(*temp > *mid_ptr ? mid_ptr++ : temp++); } else { do { *array++ = *temp++; } while (after_buff != temp); break; } } break; } else { ++array; } } while (middle != array); } } /* END mergesort.c */ -- pete |

All times are GMT. The time now is 06:48 PM. |

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.

SEO by vBSEO ©2010, Crawlability, Inc.