Sorting filerecords without an array? 
Author Message
 Sorting filerecords without an array?

Hi,

Any suggestions on how to attack this problem in TP7:

I have a file of records that I would like to sort by a field for example
"lastname". I don't want to use any array to do this. I only want to use the
fileoperators and sort the records on screen. Like picking the first record
with the lowest stringvalue, write this record to the screen then moving the
filepointer to the second lowest filerecord and so on until Eof?

Does anyone have any suggestions on how to solve this problem?

Regards,
ML



Wed, 18 Jun 1902 08:00:00 GMT  
 Sorting filerecords without an array?
ML skrev i meddelandet ...

Quote:
>Hi,

>Any suggestions on how to attack this problem in TP7:

>I have a file of records that I would like to sort by a field for example
>"lastname". I don't want to use any array to do this. I only want to use
the
>fileoperators and sort the records on screen. Like picking the first record
>with the lowest stringvalue, write this record to the screen then moving
the
>filepointer to the second lowest filerecord and so on until Eof?

>Does anyone have any suggestions on how to solve this problem?

>Regards,
>ML

Well, if you want minimal temporary storage of the contents of the file,
then you will have to read the entire file as many times as there are
records in the file, or even up to twice as many times.

Well, anyway, here goes:
1. read through the file, finding the smallest (first) value.
2. read through the file, displaying all records with that key.
3. read through the file, finding the smallest value larger than the
previous.
4. go to step 2.

Repeat this until you have displayed as many records as there are records in
the file.

If the key is unique, you only have to remember where the record was with
the best value found, and display that one, as step 2.

--
/GreenGhost
________________________
Kill the spammer to mail me



Wed, 18 Jun 1902 08:00:00 GMT  
 Sorting filerecords without an array?
i recommend doing so:

for i:=1 to Records-1 do
??? for j:=2 to records do
???? if Record[i].fleld>Record[j].field then Swap(Record[i], record[J]) {swap records}

that will do the trick.

Quote:

> ML skrev i meddelandet ...
> >Hi,

> >Any suggestions on how to attack this problem in TP7:

> >I have a file of records that I would like to sort by a field for example
> >"lastname". I don't want to use any array to do this. I only want to use
> the
> >fileoperators and sort the records on screen. Like picking the first record
> >with the lowest stringvalue, write this record to the screen then moving
> the
> >filepointer to the second lowest filerecord and so on until Eof?

> >Does anyone have any suggestions on how to solve this problem?

> >Regards,
> >ML

> Well, if you want minimal temporary storage of the contents of the file,
> then you will have to read the entire file as many times as there are
> records in the file, or even up to twice as many times.

> Well, anyway, here goes:
> 1. read through the file, finding the smallest (first) value.
> 2. read through the file, displaying all records with that key.
> 3. read through the file, finding the smallest value larger than the
> previous.
> 4. go to step 2.

> Repeat this until you have displayed as many records as there are records in
> the file.

> If the key is unique, you only have to remember where the record was with
> the best value found, and display that one, as step 2.

> --
> /GreenGhost
> ________________________
> Kill the spammer to mail me

--

?????????????????? ICQ: 14187537
??????? If Time Is Killing You - Kill Some For Time
?


Wed, 18 Jun 1902 08:00:00 GMT  
 Sorting filerecords without an array?

Quote:

> ML skrev i meddelandet ...
> >Hi,

> >Any suggestions on how to attack this problem in TP7:

> >I have a file of records that I would like to sort by a field for example
> >"lastname". I don't want to use any array to do this. I only want to use
> the
> >fileoperators and sort the records on screen. Like picking the first record
> >with the lowest stringvalue, write this record to the screen then moving
> the
> >filepointer to the second lowest filerecord and so on until Eof?

> >Does anyone have any suggestions on how to solve this problem?

> >Regards,
> >ML

> Well, if you want minimal temporary storage of the contents of the file,
> then you will have to read the entire file as many times as there are
> records in the file, or even up to twice as many times.

     Not at all!  Back in the Bad Old Days of mainframes, when even disk
space was rare, people used tape drives a lot.  Suppose you have a tape
full of records, unsorted, and want to make a tape of sorted records.
This is, I think, basically the problem that is posed here.

     The technique is essential a merge sort, in particular a form of
the sort called a Polyphase Sort.  What you do is basically as follows:

     Start with one input "tape" and N output "tapes".  Distribute the
input records onto the N output tapes so as to create the longest
possible sorted fragments as possible.  For instance, if the input had
3 4 5 2 3 6 1 2 3, you could write 3 4 5 on Tape 1, 2 3 on Tape 2, 6
back on Tape 1, 1 2 3 on Tape 3.  Eventually, you'll need to put a
smaller number on one of the tapes.  For example, if we had only 2
output tapes, you'd have to put 1 2 3 on either Tape 1 or Tape 2.

     Once you've distributed the input tape onto the N output tapes,
you now use the N tapes as "inputs" and your original input tape as an
output tape.  What you now want to do is to merge your partly-sorted
records on the N tapes into a single sorted record on the output tape.
You'll probably end up creating multiple "runs" on the output tape,
but many fewer than were on the original tape.

     Once the merge is done, you repeat the process.  Now, your "input"
tape, formerly unordered, is made up of partly-ordered runs from the
previous merge.  It should be obvious that at each distribute/merge
pass, the number of runs will be at most 1/N the number on the previous
pass.  When this decreases to 1, the array is sorted.  If you have as
few as 3 tapes, this should take at most log2(N) (where N now is the
number of records) passes.

Bob Schor
Pascal Enthusiast



Wed, 18 Jun 1902 08:00:00 GMT  
 
 [ 4 post ] 

 Relevant Pages 

1. Shell sort vs. Comb sort (was: sorting arrays)

2. lgarray0.zip TP unit for huge arrays and arrays of sorted strings

3. Sorting a TTABLE without index

4. How to sort a table without using indices?

5. How Do I display data sorted by specific fields without SQL statements

6. Sorting Paradox Tables Without Indices and Storing the Results

7. How do I increase array size without stack overflow error

8. How do I increase array size without stack overflow error

9. Getting multiple answers without arrays

10. How to randomize a sorted array?

11. Sorting Array

12. sort index in array

 

 
Powered by phpBB® Forum Software