Binary Sort

[Fulvio]

https://godbolt.org/z/czq5YY41T

[Look]

Is this one called quad sort useful ?

[dangi12012]

Code: Select all

struct uint256{
     uint64_t a,b,c,d;
     bool operator < (const uint64_t &x) const
     {
       if (a < x.a) return true;
       if (b < x.b) return true;
       if (c < x.c) return true;
       if (d < x.d) return true;
       return false;
     }
}

this code is plain wrong as you don't handle inequality on particular places
{2,1,2,3} compares less than {1,1,2,4}, for example

Since its a representation of a 256 bit value - you only need to compare each segment no?
OP asked about a special library. I point out that the question is a non starter - which is correct.

[hgm]

No.

You only have to compare less-significant segments when all more-significant segments are equal. The first non-equal segment decides.

[diep]

I browsed the internet for finding an util that can sort a binary file with a key > 64 bits and found nothing useful and so I wrote one myself. It's slow but it works. It's slow because every time the binary keys are converted to a string first before a comparison with strcmp can be made.

The example code checks sfen *.binpack files on double positions, in the binpack format the position is stored in 256 bytes and thus the sort key has the extreme size of 32 bytes.

The sfen_quicksort() routine is based on an article I once found in a magazine decades before the internet which I saved and so now and then comes in handy.

https://github.com/egh-s/Bsort

Download at - https://github.com/egh-s/Bsort/releases/tag/Bsort

I use heapsort in the root. If C code works for you, you can get that. Heapsort is garantueed O (n log n)
It works in situ.

Quicksort with hashkeys is never a good plan. If you hit a worst case performance once, that's gonna take forever.

In linux there is a couple of tools that can already do it for you in different manners if you would query them.

Always use heapsort in case you're not sure.

Quicksort is quick if your list is already kind of presorted and you expect just a few entries would need to flip.
Worst case of quicksort is horrible.

[dangi12012]

I browsed the internet for finding an util that can sort a binary file with a key > 64 bits and found nothing useful and so I wrote one myself. It's slow but it works. It's slow because every time the binary keys are converted to a string first before a comparison with strcmp can be made.

The example code checks sfen *.binpack files on double positions, in the binpack format the position is stored in 256 bytes and thus the sort key has the extreme size of 32 bytes.

The sfen_quicksort() routine is based on an article I once found in a magazine decades before the internet which I saved and so now and then comes in handy.

https://github.com/egh-s/Bsort

Download at - https://github.com/egh-s/Bsort/releases/tag/Bsort

I use heapsort in the root. If C code works for you, you can get that. Heapsort is garantueed O (n log n)
It works in situ.

Quicksort with hashkeys is never a good plan. If you hit a worst case performance once, that's gonna take forever.

In linux there is a couple of tools that can already do it for you in different manners if you would query them.

Always use heapsort in case you're not sure.

Quicksort is quick if your list is already kind of presorted and you expect just a few entries would need to flip.
Worst case of quicksort is horrible.

I like counting sort most. Its the only one with O(n) - and it can do sorting without any comparisons.
Its not applicable for hash sorting.

It is a true magic algorithm. Pass once to gather data. Second pass -> Write Perfectly sorted array inplace.

[Sesse]

My favorite idiom for this (probably also often the one with the fewest comparisons in many cases) is

Code: Select all

if (a != x.a)
  return a < x.a;
if (b != x.b)
  return b < x.b;
if (c != x.c)
  return c < x.c;
return d < x.d;

You can also just ask the compiler nicely to do it for you:

Code: Select all

return std::make_tuple(a, b, c, d) < std::make_tuple(x.a, x.b, x.c, x.d);

[dangi12012]

My favorite idiom for this (probably also often the one with the fewest comparisons in many cases) is

Code: Select all

You can also just ask the compiler nicely to do it for you:

[code]
return std::make_tuple(a, b, c, d) < std::make_tuple(x.a, x.b, x.c, x.d);

Thats cool! You also get a hashcode and all other comparisons with zero Overhead. C++ compilers will remove all tuple stuff and leave perfect comparison code

[Sesse]

No, std::hash isn't specialized for std::pair or std::tuple.