Binary Sort/Merge Sort in awk
Author Message
Binary Sort/Merge Sort in awk

Hi There,

Does any body any existence of a binary or merge sort program written in
awk to sort a list of numbers.
I see there are simple sort programs written but I can see the effect of
O(n2) complexity for large number i.e. it takes a LOT of time to sort
large amount of numbers.

Thanks
Vikas

Tue, 14 Jan 2003 03:00:00 GMT
Binary Sort/Merge Sort in awk

Quote:

> Does any body any existence of a binary or merge sort program written in
> awk to sort a list of numbers.

As always, people underestimate how useful the classic books are.

http://plan9.bell-labs.com/cm/cs/awkbook/index.html

The code for quick sort and heap sort and all the other code
examples is here:

http://plan9.bell-labs.com/cm/cs/who/bwk/awkcode.txt

+---------------------------------------------------------------------+
| Juergen Kahrs,       STN Atlas Elektronik GmbH,   D-28305 Bremen    |
| Simulation Division  Sebaldsbruecker Heerstr. 235 +49/421/457-2819  |
+----------- http://home.t-online.de/home/Juergen.Kahrs/ -------------+

Tue, 14 Jan 2003 03:00:00 GMT
Binary Sort/Merge Sort in awk

Quote:
>Does any body any existence of a binary or merge sort program written in
>awk to sort a list of numbers.
>I see there are simple sort programs written but I can see the effect of
>O(n2) complexity for large number i.e. it takes a LOT of time to sort
>large amount of numbers.

I suspect that awk will take a lot more time than sort...
On the assumption that you are working in a UNIX (lookalike) platform

Why not do a split (man split), followed by a sort
on each sub-file and then a mega merge at the end (using sort -m)

Another approach is to use awk to write out subfiles based
on the first character of the field length.
ie all records with keys beginning with 'A' go to subfileA, 'B' to subfileB etc
then you sort each of those, and use cat, rather than sort -m at the end

Mark
---
Mark Katz
Mark-it, London. Delivering MR-IT/Internet solutions
Tel: (44) 20-8731 7516, Fax: (44) 20-8458 9554
For latest information about ISPC/ITE - see http://www.e-tabs.com

Tue, 14 Jan 2003 03:00:00 GMT

 Page 1 of 1 [ 3 post ]

Relevant Pages