Need help with a Project

[dashure]

I am doing a project now in school, and i really need help!.
its goes like this:
I have 1000 triangles in a file..did it already (its a struct)every triangle has 3 points and its binary catalog number.
I have space in memory only for 200.
in this file every 200 triangles sorted by Area,and now i have to marge all the triangles together so that finally in 1 file i will have all of them sorted by Area.
i have all the functions for Area and everthing that goes with it.
i just have no idea how to do the Marge.
i can use only 2 files for backup.
for example:
array : 1,2,3,4,2,5,8,9,4,6,8,10
and now i have only 4 spaces in memory .
i have to get in file
array: 1,2,2,3,4,4,5,6,8,8,9,10
i can use 2 extra files for help.

Have any idea?

[dashure]

and the function have to work for 600 triangles ,or if i would change the number of triangles (not 1000) that it will still work

[TrustyTony]

What if you knew next value of each sorted file? Could you find the next sorted value in result file? Try it yourself with arranged values in pieces of papers in four piles and produce result pile (you must put the chosen pieces to result pile upside down and turn it in the closing operatiom to produce queue, not stack)

[dashure]

well, i tried everything i have no idea how to do it.
and i didn't understand what you mean..
i have one file will 1000 triangle and every 200 are sorted by area from the smallest to the biggest..so its like, 1,2,3,4,2,5,6,7,1,2,3,5
and it should be: 1,1,2,2,2,3,3,4,5,5,6,7

[TrustyTony]

1,2,3,4
2,5,6,7,
1,2,3,5

[dashure]

but i am telling you, its all in the same FILE!
it should be something like this:
i should take 50 from the first 200 and 50 from the second 200 and marge it and than put it in file than, take another 50 and so on...i dont know..
if you could write a code what you mean or anything in a code..it would give much more help

[TrustyTony]

OK, I am not going to give you ready answer so here some fragment of Python code as pseudo code, you must transform it to operate with file and to scan the seek positions of each part instead of using values in memory (one file pointer to each part)

def do_merge(values, section_length):
    print('This code will merge %i parts of length %i' % ( len(values) // section_length,
                                                           section_length))
    for pos in range(0,len(values),section_length):
        print(values[pos:pos + section_length])
    print('First result value is %i' % min(values[::section_length]))

values = [1,2,3,4,2,5,6,7,1,2,3,5]
prev = values[0] - 1
# You must change this to take the values from file one by one
for index in range(len(values)):
    current = values[index]
    if  current < prev:
        partlength = index
        break
    else:
        prev = current
do_merge(values, partlength)

'''Output:
This code will merge 3 parts of length 4
[1, 2, 3, 4]
[2, 5, 6, 7]
[1, 2, 3, 5]
First result value is 1
'''

[dashure]

well thanks, but it still doesnt help me!
i am a student i learn C lang,
i need it simple, dont know python.

but thanks anyway.

[TrustyTony]

If you are student of C, you must write the C. We are helping in school work but do not do it for others. Show us some code and we can help you through hurdles.

As more pseudo pseudo-code:

1. Scan file for first lower value, record the length of section
2. Set file pointer in beginning of each section
3. Do merge until all parts are consumed outputting the values to result file by
   • taking the smallest value read and read next value from that section if less than section length values read from that section

.

[dashure]

its all ok, but i have only space for 200 triangles in memory, and what if the user tells me to make only 600 not 1000 triangles..
this function should be good for every amount of triangels.
for example: i take 50 first and than another 50 from second section (now it took 100 space in memory),,so the merge i put to another 100 and copy it to a file,
than take another 50 from first and 50 from second. and merge and put it in another fill..and so on.
but my question is , i dont know how many files i need?(i can use only 2 files ).

[dashure]

19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1 0
16 61 45 54 22 2 8 9 11 7 5 55 33 3 11 1 51 6 4 23
61 54 45 22 16 11 9 8 7 2 55 51 33 23 11 6 5 4 3 1
6 5 4 3 2 1 11 9 8 7 2 6 5 4 3 1
11 9 8 7 6 5 4 3 2 1 11 9 8 7 55 51 33 23 11
11 11 55 51 33 23
55 54 51 45 33 23 22 16 11 61 54 45 22 16 55 51 33 23
61 55 54 54 45 33 23 22 16 11 61

11 9 8 7 6 5 4 3 2 1
61 55 54 54 45 33 23 22 16 11 11 9 8 7 6 5 4 3 2 1

[TrustyTony]

You only need single value of each part and output can be directly written to file.

[TrustyTony]

If you need to do it in single pass, you can use those two files: another is merged output and other is merged input and after each part they exchange roles.

[dashure]

you mean i should put in memory only the first value of each section than marge and put in file?

[TrustyTony]

minimum of file must be one of minimums of parts. But that way you must scan the file for th breaks of parts and second time for merge. On the other hand we produce the result with one write. In second alternative you must write to file the values on average half the number of parts times which looks more expensive for me, but I could be wrong.

[dashure]

i think i should ask my question again:
i have a buffer of 200 and a FILE of 1000 triangles and in this file every 200 triangles are sorted by area.
so the algorithm goes like this:
i take first 50 triangles from the first 200 triangles and 50 from the second 200, put both of them in buffer ( i have 100 more space in buffer )..so the marge that will be 100 triangles goes to this 100 space, than i put this 100 to a NEW file!.
than i take another 50 from from first and another 50 from second and do the same. and so on till i have 400 marged triangles in NEW file!.
and i do the same for another 400 triangles and put it in another NEW file.
and now i have 2 files of 400 sorted triangles.
now i take the last 200 triangles( from the first file where there were 1000 triangels that every 200 was sorted)..and this 200 i merge with one of the 400 triangles in a New file.and put it in new file.

NOW i have 1 file with 400 triangles sorted and another file with 600(400+200) triangles sorted. so now i merge this 2 files in one NEW FILE which now contains 1000 sorted triangles.
________________________________
all this function should be general, i mean if i change the buffer size to 600 than i will take 150 triangles from first 200 and 150 from second 200 and merge it and put it in 300 space i have left in the buffer.
and than after all this same done, antil there is a sorted new fill with 1000 triangles.
So my main question is that this function should be global for any different size of buffer,so How many files should i take?
in 200 space buffer i use 4 files and than delete 3 of them and stay with the 1 FILE with 1000 triangles sorted, and when you have a 600 buffer i need 3 file or 1 i guess not sure..

[TrustyTony]

No, OK, let's explain this file using version in detail

Start condition: We have unknown amount of parts in one file of triangles, first value of second part has bigger triangle than last in first partition.

Merged input <- empty file
partitionlength <- -1

while not eof:

Merged output <- overwrite with values of smaller of next triangle in input files part or merged inputs next triangle or if one is empty, from other one, terminate if next triangle is smaller than previous if partition length = -1, else read partitionlength values

Swap Merged input and Merged output, set partionlength of part for consistency check and loop counter, if partitionlength was -1

Merged output is our fully sorted file, we needed only two triangles worth working memory and two files plus some scalar variables.

[TrustyTony]

...read partitionlength values from input part of original file or eof reached in both input files

In the end the result will be set to merged input due to last swap action if break is not used to pass the swap and exit the loop. at eof we must continue to consume values from merged input until it reach eof, last part could have less than partitionlength values if partitionlength does not divide number of triangles