libhatchet
Loading...
Searching...
No Matches
Classes | Typedefs | Functions
hxradix_sort.hpp File Reference

Go to the source code of this file.

Classes

class  hxradix_sort_key< key_t_, value_t_ >

Typedefs

using hxradix_sort_key_void = hxradix_sort_key<uint32_t, void*>

Functions

void hxradix_sort_void (hxradix_sort_key_void *begin_, hxradix_sort_key_void *end_, hxsystem_allocator_t allocator_)
void hxradix_sort_void11 (hxradix_sort_key_void *begin_, hxradix_sort_key_void *end_, hxsystem_allocator_t allocator_)
template<typename key_t_, typename value_t_>
void hxradix_sort (hxradix_sort_key< key_t_, value_t_ > *begin_, hxradix_sort_key< key_t_, value_t_ > *end_, hxsystem_allocator_t allocator_)
template<typename key_t_, typename value_t_>
void hxradix_sort11 (hxradix_sort_key< key_t_, value_t_ > *begin_, hxradix_sort_key< key_t_, value_t_ > *end_, hxsystem_allocator_t allocator_)

Detailed Description

Θ(n) radix sort for 32-bit-or-smaller scalar keys.

Typedef Documentation

◆ hxradix_sort_key_void

using hxradix_sort_key_void = hxradix_sort_key<uint32_t, void*>

hxradix_sort_key_void - Internal.

Used to share the implementation with all pointer types.

Function Documentation

◆ hxradix_sort()

template<typename key_t_, typename value_t_>
void hxradix_sort ( hxradix_sort_key< key_t_, value_t_ > * begin_,
hxradix_sort_key< key_t_, value_t_ > * end_,
hxsystem_allocator_t allocator_ )

hxradix_sort - Sorts an array of hxradix_sort_key<key_t, value_t> by key_t using 8-bit digits.

key_t is the sort key and value_t the value being sorted. Keys of double, int64_t, and uint64_t are not supported. This is an Θ(n) algorithm that does not cause code bloat and is the fastest sorting algorithm available for scalar keys. Radix sort is best when you need real-time guarantees and have a massive workload. IBM used it to sort punch cards. hxradix_sort scales linearly with the byte-length of the key, whereas hxinsertion_sort is Θ(n) on mostly sorted data.

For example:

hxvector<hxradix_sort_key<key_t, example_t*>> rs; rs.reserve(size);
for(uint32_t i = size; i--;) {
rs.push_back(hxradix_sort_key<key_t, example_t*>(x[i].id, &x[i]));
}
hxradix_sort(rs.begin(), rs.end(), hxsystem_allocator_heap);
hxradix_sort_key
hxradix_sort_key - A key-value pair used with hxradix_sort.
Definition hxradix_sort.hpp:22
hxvector
hxvector - Implements std::vector, std::inplace_vector and std::back_insert_iterator with a few thing...
Definition hxvector.hpp:82
hxvector::begin
const T * begin(void) const
Returns a const T* to the beginning of the array.
Definition hxvector.hpp:280
hxvector::push_back
T & push_back(args_t_ &&... args_) noexcept
Appends an element to the end of the array.
hxvector::end
const T * end(void) const
Returns a const T* to the end of the array.
Definition hxvector.hpp:328
hxvector::reserve
void reserve(hxsize_t size_, hxsystem_allocator_t allocator_=hxsystem_allocator_current, hxalignment_t alignment_=hxalignment)
Reserves storage for at least the specified number of elements.
hxsystem_allocator_heap
@ hxsystem_allocator_heap
hxsystem_allocator_heap - OS heap with alignment.
Definition hxmemory_manager.h:84
hxradix_sort
void hxradix_sort(hxradix_sort_key< key_t_, value_t_ > *begin_, hxradix_sort_key< key_t_, value_t_ > *end_, hxsystem_allocator_t allocator_)
hxradix_sort - Sorts an array of hxradix_sort_key<key_t, value_t> by key_t using 8-bit digits.
Definition hxradix_sort.hpp:130
  • begin : Non-null pointer to the first element in the range being reordered.
  • end : Non-null pointer one past the last element in the range. Must reference the same array as begin.
  • allocator : The allocator used for the temporary working buffers.

◆ hxradix_sort11()

template<typename key_t_, typename value_t_>
void hxradix_sort11 ( hxradix_sort_key< key_t_, value_t_ > * begin_,
hxradix_sort_key< key_t_, value_t_ > * end_,
hxsystem_allocator_t allocator_ )

hxradix_sort11 - Sorts an array of hxradix_sort_key<key_t, value_t> by key_t using 11-bit digits.

key_t is the sort key and value_t the value being sorted. Keys of double, int64_t, and uint64_t are not supported. hxradix_sort scales linearly with the byte-length of the key, whereas hxinsertion_sort is Θ(n) on mostly sorted data.

  • begin : Non-null pointer to the first element in the range being reordered.
  • end : Non-null pointer one past the last element in the range. Must reference the same array as begin.
  • allocator : The allocator used for the temporary working buffers.

◆ hxradix_sort_void()

void hxradix_sort_void ( hxradix_sort_key_void * begin_,
hxradix_sort_key_void * end_,
hxsystem_allocator_t allocator_ )

hxradix_sort_void - Internal.

The shared implementation used with all pointer types when sorting using 8-bit digits.

  • begin : Non-null pointer to the first element in the range being reordered.
  • end : Non-null pointer one past the last element in the range. Must reference the same array as begin.
  • allocator : The allocator used for the temporary working buffers.

◆ hxradix_sort_void11()

void hxradix_sort_void11 ( hxradix_sort_key_void * begin_,
hxradix_sort_key_void * end_,
hxsystem_allocator_t allocator_ )

hxradix_sort_void11 - Internal.

The shared implementation used with all pointer types when sorting using 11-bit digits.

  • begin : Non-null pointer to the first element in the range being reordered.
  • end : Non-null pointer one past the last element in the range. Must reference the same array as begin.
  • allocator : The allocator used for the temporary working buffers.