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

  vikas.sapra.vcf
< 1K Download


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.
Read this one:

  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  
 
 [ 3 post ] 

 Relevant Pages 

1. Sorting Tables with sort-merge ??

2. Qsort, Merge sort, Radix sort in prolog Help!

3. sort, merge, or insertion sort?

4. Straight Insertion Sort and Binary Insertion Sort

5. Merge sort

6. Parallel Merge Sort

7. merge sort

8. How to write merge sort by Assembly Language

9. Question about SORT-MERGE.

10. Error 223 - Sort/Merge...Please help!

11. Sort and Merge problem

12. Function to merge sorted lists

 

 
Powered by phpBB® Forum Software