By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
446,413 Members | 999 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 446,413 IT Pros & Developers. It's quick & easy.

About Sorting

P: n/a
mhk
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
Share this Question
Share on Google+
5 Replies


P: n/a

"mhk" <cc*****@dddsssl.com> 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;
<yor_item_type> 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(<input_file>) /*if an input file exists*/);
HTH
Robert
Nov 13 '05 #2

P: n/a
mhk
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" <cc*****@dddsssl.com> 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;
<yor_item_type> 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(<input_file>) /*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.
<http://cbfalconer.home.att.net> 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 <cc*****@dddsssl.com> 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 but
i dont know its algorithem.

can anyone tell me algorithm of 3 way merge sort or anyother way to
solve 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
<<Remove the del for email>>
Nov 13 '05 #6

This discussion thread is closed

Replies have been disabled for this discussion.