Last active
August 29, 2015 14:27
-
-
Save augustlate/691d5c192788e33745a4 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // Copyright August Late 2015 | |
| // Licence: Public Domain | |
| template<typename K,typename V,unsigned int RADIXSORT_BITS> | |
| void RadixSort(K * _keys,K *_tempKeys,V * _values, V * _tempValues, size_t _size) | |
| { | |
| static_assert(std::is_unsigned<K>::value,"Key type must be of an unsigned integral type"); | |
| constexpr unsigned int RADIXSORT_HISTOGRAM_SIZE = (1<<RADIXSORT_BITS); | |
| constexpr unsigned int RADIXSORT_BIT_MASK = (RADIXSORT_HISTOGRAM_SIZE-1); | |
| constexpr unsigned int PASSES = sizeof(K)*8/RADIXSORT_BITS+(sizeof(K)*8%RADIXSORT_BITS != 0 ? 1 : 0); | |
| uint32_t histogram[RADIXSORT_HISTOGRAM_SIZE]; | |
| uint32_t pass = 0; | |
| uint16_t shift = 0; | |
| K * keys = _keys; | |
| K * tempKeys = _tempKeys; | |
| V * values = _values; | |
| V * tempValues = _tempValues; | |
| for(; pass < PASSES; ++pass) | |
| { | |
| memset(histogram, 0, sizeof(uint32_t)*RADIXSORT_HISTOGRAM_SIZE); | |
| bool sorted = true; | |
| { | |
| K key = keys[0]; | |
| K prevKey = key; | |
| for (uint32_t ii = 0; ii < _size; ++ii, prevKey = key) | |
| { | |
| key = keys[ii]; | |
| uint16_t index = (key>>shift)&RADIXSORT_BIT_MASK; | |
| ++histogram[index]; | |
| sorted &= prevKey <= key; | |
| } | |
| } | |
| if(sorted) goto done; | |
| uint32_t offset = 0; | |
| for (uint32_t ii = 0; ii < RADIXSORT_HISTOGRAM_SIZE; ++ii) | |
| { | |
| uint32_t count = histogram[ii]; | |
| histogram[ii] = offset; | |
| offset += count; | |
| } | |
| for (uint32_t ii = 0; ii < _size; ++ii) | |
| { | |
| K key = keys[ii]; | |
| uint16_t index = (key>>shift)&RADIXSORT_BIT_MASK; | |
| uint32_t dest = histogram[index]++; | |
| tempKeys[dest] = key; | |
| tempValues[dest] = values[ii]; | |
| } | |
| std::swap(tempKeys,keys); | |
| std::swap(tempValues,values); | |
| shift += RADIXSORT_BITS; | |
| } | |
| done: | |
| if(0 != (pass & 1)){ | |
| memcpy(_keys, _tempKeys, _size*sizeof(K) ); | |
| for (uint32_t ii = 0; ii < _size; ++ii) | |
| { | |
| _values[ii] = _tempValues[ii]; | |
| } | |
| } | |
| return; | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment