가리지말고 radix_sort 하자~

[mozzart(mozzart)]

#include <string.h>

#if     _MSC_VER && !__INTEL_COMPILER

  #define MSVC

  #include <malloc.h>

#else

  #include <alloca.h>

#endif

//------------------------------------------------------------------------------

#define rigid                   constexpr

using   i8  = char;

using   i16 = short;

using   i32 = int;

using   i64 = long long;

using   u8  = unsigned char;

using   u16 = unsigned short;

using   u32 = unsigned int;

using   u64 = unsigned long long;

using   f32 = float;

using   f64 = double;

#if     _WIN64 || __x86_64__ || __ppc64__

  #define SYS64

  using   iu = u64;

#else

  #define SYS32

  using   iu = u32;

#endif

#define countof( arr )          ( sizeof arr / sizeof *arr )

#define CHAR_BITS               8

//------------------------------------------------------------------------------

template< typename T >

inline  rigid   iu      msb_position()

{

    return  sizeof( T ) * CHAR_BITS - 1;

}

template< typename T >

inline  rigid   auto    msb_value()

{

    return  1ULL << msb_position< T >();

}

#define msb_pos( var ) msb_position< decltype( var ) >()

#define msb_val( var ) msb_value< decltype( var ) >()

//------------------------------------------------------------------------------

inline  void        real2uexp( const f32& r )

{

    *(i32*)&r ^= *(i32*)&r >> msb_pos( r ) | msb_val( r );

}

inline  void        uexp2real( const f32& r )

{

    *(i32*)&r ^= ~*(i32*)&r >> msb_pos( r ) | msb_val( r );

}

inline  void        real2uexp( const f64& r )

{

    const   u32 c = *( (i32*)&r + 1 ) >> msb_position< i32 >();

    *(u32*)&r ^= c;

    *( (u32*)&r + 1 ) ^= c | msb_val( c );

}

inline  void        uexp2real( const f64& r )

{

    const   u32 c = ~( *( (i32*)&r + 1 ) >> msb_position< i32 >() );

    *(u32*)&r ^= c;

    *( (u32*)&r + 1 ) ^= c | msb_val( c );

}

//------------------------------------------------------------------------------

#include <type_traits>

template< u32 BUCKET_BITS, typename T >

inline  void    count_sort( const T* src, const u32 size )

{

    if( !size ) return;

    rigid   u32 EXPRESSION_SIZE = 1 << BUCKET_BITS;

    rigid   u32 MASK = EXPRESSION_SIZE - 1;

    T*  dst;

    dst = (T*)src;

    const   u32 h = !std::is_floating_point< T >() && std::is_signed< T >() ?

                    msb_val( *src ) : 0;

    u32  counts[ EXPRESSION_SIZE ] = { 0 };

    {

        const T* end = src + size;

        while( dst < end ) counts[ *dst++ + h & MASK ]++;

    }

    dst = (T*)src;

    for( u32 c = 0; c < EXPRESSION_SIZE; ++c )

    {

        const T* end = dst + counts[ c ];

        const int cc = c - h;        

        while( dst < end ) *dst++ = cc;

    }

}

///-----------------------------------------------------------------------------

template< u32 BUCKET_BITS, u32 ORDER, typename T >

inline  void    radix( T* dst, const T* src, const u32 size )

{

    rigid   u32 EXPRESSION_SIZE = 1 << BUCKET_BITS;

    rigid   u32 MASK = EXPRESSION_SIZE - 1;

    rigid   u32 BIT_ORDER = ORDER * BUCKET_BITS;

    u32  counts[EXPRESSION_SIZE] = { 0 };

    u32  indices[EXPRESSION_SIZE];

    for( u32 i = 0; i < size; ++i )

        counts[src[i] >> BIT_ORDER & MASK]++;

    indices[0] = 0; indices[1] = counts[0];

    for( u32 i = 1; i < MASK; ++i )

        indices[i + 1] = indices[i] + counts[i];

    for( u32 i = 0; i < size; ++i )

        dst[indices[src[i] >> BIT_ORDER & MASK]++] = src[i];

}

#include <type_traits>

template< typename T >

inline  void    radix_sort( T* src, const u32 size )

{

    if( !size ) return;

    if( !std::is_floating_point< T >() && std::is_signed< T >() )

        for( u32 i = 0; i < size; ++i )

            src[ i ] += msb_val( *src );

    T*  tmp;

    if( size >= 4096 )

        tmp = new T[size];

    else

        tmp = (T*)alloca( sizeof *src * size );

    rigid   u32 BUCKET_BITS = sizeof( T ) > 4 ? 16 : 8;

    radix< BUCKET_BITS, 0 >( tmp, src, size );

    radix< BUCKET_BITS, 1 >( src, tmp, size );

    if( sizeof *src > 2 )

    {

        radix< BUCKET_BITS, 2 >( tmp, src, size );

        radix< BUCKET_BITS, 3 >( src, tmp, size );

    }

    if( size >= 4096 )

    {

        delete[] tmp;

    }

    if( !std::is_floating_point< T >() && std::is_signed< T >() )

        for( u32 i = 0; i < size; ++i )

            src[ i ] -= msb_val( *src );

}

inline  void    radix_sort( u8* src, const u32 size )

{

    count_sort< 8 >( src, size );

}

inline  void    radix_sort( i8* src, const u32 size )

{

    count_sort< 8 >( src, size );

}

inline  void    radix_sort( f32* src, const u32 size )

{

    for( u32 i = 0; i < size; ++i )

        real2uexp( src[i] );

    radix_sort( (u32*)src, size );

    for( u32 i = 0; i < size; ++i )

        uexp2real( src[i] );

}

inline  void    radix_sort( f64* src, const u32 size )

{

    for( u32 i = 0; i < size; ++i )

        real2uexp( src[i] );

    radix_sort( (u64*)src, size );

    for( u32 i = 0; i < size; ++i )

        uexp2real( src[i] );

}

//------------------------------------------------------------------------------

#include <iostream>

using   namespace   std;

int main()

{

    u8  arr_u8[] = { 5, 4, 3, 2, 1, 0, (u8)-1, (u8)-2, (u8)-3, (u8)-4, (u8)-5 };

    radix_sort( arr_u8, countof( arr_u8 ) );

    for( const auto v : arr_u8 )

        cout << (f64)v << " ";

    cout << endl;

    i8  arr_i8[] = { 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5 };

    radix_sort( arr_i8, countof( arr_i8 ) );

    for( const auto v : arr_i8 )

        cout << (f64)v << " ";

    cout << endl;

    i16 arr_i16[] = { 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5 };

    radix_sort( arr_i16, countof( arr_i16 ) );

    for( const auto v : arr_i16 )

        cout << (f64)v << " ";

    cout << endl;

    i32 arr_i32[] = { 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5 };

    radix_sort( arr_i32, countof( arr_i32 ) );

    for( const auto v : arr_i32 )

        cout << (f64)v << " ";

    cout << endl;

    f32 arr_f32[] = { 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5 };

    radix_sort( arr_f32, countof( arr_f32 ) );

    for( const auto v : arr_f32 )

        cout << (f64)v << " ";

    cout << endl;

    f64 arr_f64[] = { 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5 };

    radix_sort( arr_f64, countof( arr_f64 ) );

    for( const auto v : arr_f64 )

        cout << (f64)v << " ";

    cout << endl;

    i64 arr_i64[] = { 5, 4, 3, 2, 1, 0, -1, -2, -3, -4, -5 };

    radix_sort( arr_i64, countof( arr_i64 ) );

    for( const auto v : arr_i64 )

        cout << (f64)v << " ";

    cout << endl;

    return 0;

}

결과 :

0 1 2 3 4 5 251 252 253 254 255 

-5 -4 -3 -2 -1 0 1 2 3 4 5 

-5 -4 -3 -2 -1 0 1 2 3 4 5 

-5 -4 -3 -2 -1 0 1 2 3 4 5 

-5 -4 -3 -2 -1 0 1 2 3 4 5 

-5 -4 -3 -2 -1 0 1 2 3 4 5 

-5 -4 -3 -2 -1 0 1 2 3 4 5

[mozzart(mozzart)]

양수고 음수고 부동소수고 그냥 막!

[ㅎㅎ(112.159)]

존나잘하시네요^^

[☎2.73™(roidz)]

담에 sort용 전용으로 최적화 된 것 하나 만들어 둘 필요 있을때 참조 해봄. ㅇㅇ

[mozzart(mozzart)]

ㅇㅇ 16000 개 이상 정렬할때, 값의 표현범위가 적을때 좋아유~

[ㅊㄹ(223.62)]

오늘 밤에 전에 만든 힙소트로 2^16 정수 데이터 정렬 해보려고 하는데 요것도 시험해봐야겠아용

[mozzart(mozzart)]

넵~

[ㅎㅎ(112.159)]

다시봐도 대단

[dddd(118.47)]

역시 코세님.. ㅎㄷㄷ 한 코딩 실력 ㄷㄷㄷㄷㄷ 존경합니다.

[dddd(118.47)]

코세님 using i64 = long long; <- 이렇게 using을 사용하는건 처음보는데.. typedef 같은 효과 인가요???

[mozzart(mozzart)]

네 같아유~

[dddd(118.47)]

아아! typedef 대신 using을 사용하면 좋은 점이 있나여??

[dddd(118.47)]

부동소수 코세님이 알려준대로 해보려다가 복잡해서 보류했었는데, 코세님 코드 보고 다시 해볼게요 ㅋ

[mozzart(mozzart)]

표현이 더 깔끔하죠 다른 대입식과 형식이 같아서 좋은것.

[dddd(118.47)]

감사합니다!!