446,148 Members | 1,342 Online
Need help? Post your question and get tips & solutions from a community of 446,148 IT Pros & Developers. It's quick & easy.

 P: n/a Hi , is there any way to merge three sorted arrays into a sorted file, without using 4th array. i guess 3 way merge sort is the only option but i dont know its algorithem. can anyone tell me algorithm of 3 way merge sort or anyother way to solve this problem. Thank you veryyyyy much. Jeff Nov 13 '05 #1
5 Replies

 P: n/a "mhk" schrieb im Newsbeitrag news:3F**************@dddsssl.com... Hi , is there any way to merge three sorted arrays into a sorted file, This is not clear to me (maybe my english): Do you already have a file with some sorted content and want to merge the arrays into it or do you just want to merge the arrays and write the merged result? However, the solution below should work similar in both cases.. without using 4th array. i guess 3 way merge sort is the only option but i dont know its algorithem. can anyone tell me algorithm of 3 way merge sort or anyother way to solve this problem. There should be no problem. Just fopen() your output file, use three indices into your sorted arrays, compare the contents at the indices and write the next matching to the file, incrementing the index of that array. (untested pseudocode only) size_t i = 0; size_t j = 0; size_t k = 0; some_var; /*if you have a sorted input file*/ /*If you want to merge into an existing sorted file, open input file and test for success*/ /*open output file and test for success*/ do { /*If you have a sorted input file, read one item from it into some_var(whatever type it may be in your case)*/ /*find the max or min (depending on your sort order) of array1[i], array2[j], array3[k], and some_var if you have an input file*/ /*write it to the file*/ /*depending on which was max or min*/ /*i++; or j++; or k++; or read the next item from the input file if you have one */ }while(i < sizeof array1 || j < sizeof array2 || k < sizeof array3 || !feof() /*if an input file exists*/); HTH Robert Nov 13 '05 #2

 P: n/a Thanks Robert, i just have three sorted arrays ,and i have to merge all three arrays into an empty file such that the file is also sorted. thanks jeff ************************************************** * Robert Stankowic wrote: "mhk" schrieb im Newsbeitrag news:3F**************@dddsssl.com...Hi ,is there any way to merge three sorted arrays into a sorted file, This is not clear to me (maybe my english): Do you already have a file with some sorted content and want to merge the arrays into it or do you just want to merge the arrays and write the merged result? However, the solution below should work similar in both cases..without using 4th array. i guess 3 way merge sort is the only option buti dont know its algorithem.can anyone tell me algorithm of 3 way merge sort or anyother way tosolve this problem. There should be no problem. Just fopen() your output file, use three indices into your sorted arrays, compare the contents at the indices and write the next matching to the file, incrementing the index of that array. (untested pseudocode only) size_t i = 0; size_t j = 0; size_t k = 0; some_var; /*if you have a sorted input file*/ /*If you want to merge into an existing sorted file, open input file and test for success*/ /*open output file and test for success*/ do { /*If you have a sorted input file, read one item from it into some_var(whatever type it may be in your case)*/ /*find the max or min (depending on your sort order) of array1[i], array2[j], array3[k], and some_var if you have an input file*/ /*write it to the file*/ /*depending on which was max or min*/ /*i++; or j++; or k++; or read the next item from the input file if you have one */ }while(i < sizeof array1 || j < sizeof array2 || k < sizeof array3 || !feof() /*if an input file exists*/); HTH Robert Nov 13 '05 #3

 P: n/a mhk wrote: is there any way to merge three sorted arrays into a sorted file, without using 4th array. i guess 3 way merge sort is the only option but i dont know its algorithem. can anyone tell me algorithm of 3 way merge sort or anyother way to solve this problem. It bears a startling resemblance to the problem of selecting the minimum (or maximum) from among three possibilities. It is not a C language problem, thus off-topic here. -- Chuck F (cb********@yahoo.com) (cb********@worldnet.att.net) Available for consulting/temporary embedded and systems. USE worldnet address! Nov 13 '05 #4

 P: n/a mhk wrote: Thanks Robert, i just have three sorted arrays ,and i have to merge all three arrays into an empty file such that the file is also sorted. Then do precisely what Robert suggested. Set each index to 0, compare indices, find the smallest, stick it in the file and bump that index, continue until you run out of data. -- Richard Heathfield : bi****@eton.powernet.co.uk "Usenet is a strange place." - Dennis M Ritchie, 29 July 1999. C FAQ: http://www.eskimo.com/~scs/C-faq/top.html K&R answers, C books, etc: http://users.powernet.co.uk/eton Nov 13 '05 #5

 P: n/a On Sun, 23 Nov 2003 09:51:05 -0600, mhk wrote: Hi ,is there any way to merge three sorted arrays into a sorted file,without using 4th array. i guess 3 way merge sort is the only option buti dont know its algorithem.can anyone tell me algorithm of 3 way merge sort or anyother way tosolve this problem. Sorted arrays a1, a2, and a3. Indexes i1, i2, and i3. File f. Pseudo code: i1 = i2 = i3 =0 while (1) if (a1[i1] < a2[i2]) if (a1[i1] < a3[i3]) fwrite(&a1[i1], sizeof *a1, 1, f) i1++ else fwrite(&a3[i3], sizeof *a3, 1, f) i3++ else if (a2[i2] < a3[i3]) fwrite(&a2[i2], sizeof *a2, 1, f) i2++ else fwrite(&a3[i3], sizeof *a3, 1, f) i3++ No fourth array at all. You need additional logic to handle: different length arrays the fact that two of the arrays will be exhausted before the third when to terminate the loop <> Nov 13 '05 #6

### This discussion thread is closed

Replies have been disabled for this discussion.