equal
deleted
inserted
replaced
252 RadixSortSelector<Value>::sort(first, last, Identity<Value>()); |
252 RadixSortSelector<Value>::sort(first, last, Identity<Value>()); |
253 } |
253 } |
254 |
254 |
255 template <typename Value> |
255 template <typename Value> |
256 unsigned char valueByte(Value value, int byte) { |
256 unsigned char valueByte(Value value, int byte) { |
257 return *((unsigned char *)(&value) + byte); |
257 return value >> (std::numeric_limits<unsigned char>::digits * byte); |
258 } |
258 } |
259 |
259 |
260 template <typename Functor, typename Key> |
260 template <typename Functor, typename Key> |
261 void counterIntroSort(Key *first, Key *last, Key *target, |
261 void counterIntroSort(Key *first, Key *last, Key *target, |
262 int byte, Functor functor) { |
262 int byte, Functor functor) { |
363 Key *buffer; |
363 Key *buffer; |
364 buffer = allocator.allocate(2 * length); |
364 buffer = allocator.allocate(2 * length); |
365 try { |
365 try { |
366 bool dir = true; |
366 bool dir = true; |
367 std::copy(first, last, buffer); |
367 std::copy(first, last, buffer); |
368 for (int i = 0; i < sizeof(Value); ++i) { |
368 for (int i = 0; i < (int)sizeof(Value); ++i) { |
369 if (dir) { |
369 if (dir) { |
370 counterIntroSort(buffer, buffer + length, buffer + length, |
370 counterIntroSort(buffer, buffer + length, buffer + length, i, functor); |
371 i, functor); |
|
372 } else { |
371 } else { |
373 counterIntroSort(buffer + length, buffer + 2 * length, buffer, |
372 counterIntroSort(buffer + length, buffer + 2 * length, buffer, i, functor); |
374 i, functor); |
|
375 } |
373 } |
376 dir = !dir; |
374 dir = !dir; |
377 } |
375 } |
378 if (dir) { |
376 if (dir) { |
379 std::copy(buffer, buffer + length, first); |
377 std::copy(buffer, buffer + length, first); |
423 /// the integer. The algorithm can sort the items on a given byte. |
421 /// the integer. The algorithm can sort the items on a given byte. |
424 /// First time it counts how many times occurs a byte value in the container. |
422 /// First time it counts how many times occurs a byte value in the container. |
425 /// By the occurence number it is possible to copy the container |
423 /// By the occurence number it is possible to copy the container |
426 /// in the right order in \c O(n) time. The algorithm sorts the container |
424 /// in the right order in \c O(n) time. The algorithm sorts the container |
427 /// by each bytes in forward direction which sorts the container by the |
425 /// by each bytes in forward direction which sorts the container by the |
428 /// whole value. This way, let be |
426 /// whole value. This way, let be \c c the maximal capacity of the integer |
429 /// \c c the maximal capacity and \c n the number of the items in |
427 /// type and \c n the number of the items in |
430 /// the container, the time complexity of the algorithm \c O(log(c)*n) |
428 /// the container, the time complexity of the algorithm \c O(log(c)*n) |
431 /// and the additional space complexity is \c O(n). |
429 /// and the additional space complexity is \c O(n). |
432 /// |
430 /// |
433 /// This sorting algorithm is stable so the order of two equal element |
431 /// This sorting algorithm is stable so the order of two equal element |
434 /// stay in the same order. |
432 /// stay in the same order. |