Sorting Table/File

[UlliN]

Hello world,

here's the "weekend algo" for your delight: an algorithm sorting tables and even files (containing records of fixed length).
TabSort sorts a table pT of N records each with length L in ascending order by sortposition P with sortkey length K :

invoke TabSort, pT, P, K, L, N

Tabsort consists of a quicksort inner loop (finding the correct position of the pivot-element) and the iterative processing of this loop. The stack is used for storing the start/end-indices at each iteration step.
Included StrComp for string comparison and SwapString for swapping two strings.

The ZIP comes with an example file (985kb) to be sorted, a program showing the use of TabSort and Makeit.bat.
Just run Makeit.bat and TestTabSort.exe.

As always improvement is appreciated ;-)

Regards
Ulli




[attachment deleted by admin]

[ramguru]

I'm looking for algo that can sort array of 2*DWORD elements ascending :
   foldpt_offset           dd 102 dup (?) ; key elements
   foldpt_number           dd 102 dup (?)
Looked at hutch's library, but there is no easy way I can modify combsort (or onother), 'cause all registers are used.
Your algo sorts strings, maybe you have something suitable for me, and this can be solved w/o great brain activity (mine  :bg )

[UlliN]

Hi ramguru,

one easy thing to do is  BSWAP the DWORDs before using TabSort and BSWAP the result afterwards. The problem in sorting strings  lexicographically (means  A<B)  is the "wrong" INTEL-byte order.

Regards,
Ulli

[hutch--]

ramguru,

Integer sorts are a lot easier to write than string sorts as the comparisons are easier and faster and depending on the number range there are very fast ways to sort integers that don't use exchange sorts at all.

If you number range is less than a few million, you use a "pidgeon hole" sort which is effectively an array of the sort size elements all set to zero at start and for each instance of a value within that range you increment the location in the array. When you have finished you perform a linear scan of the array expanding each non zero value to the number of instances and write them back in order.

This technique will kill an exchange sort stone dead no matter what type it is.

[ramguru]

Thanks for suggestion Hutch. I actually did it in other way, with no need of sorting.
1.Found index where I needed to insert new record
2.Used RtlMoveMemory (this func is useful when memory overlaps) to resize both arrays
3.Inserted new record in appr. place