About Sorting

[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

[Robert Stankowic]

"mhk" <cc*****@dddsss l.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_typ e> 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(whatev er 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_fi le>) /*if an input file exists*/);
HTH
Robert

[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*****@dddsss l.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_typ e> 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(whatev er 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_fi le>) /*if an input file exists*/);
HTH
Robert

[CBFalconer]

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********@yah oo.com) (cb********@wor ldnet.att.net)
Available for consulting/temporary embedded and systems.
<http://cbfalconer.home .att.net> USE worldnet address!

[Richard Heathfield]

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.pow ernet.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

[Barry Schwarz]

On Sun, 23 Nov 2003 09:51:05 -0600, mhk <cc*****@dddsss l.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>>