マルチキークイックソート ( multi-key quick sort )

ケンキュウシツの先輩が前から進捗報告で話してるのを見ていてなんだろうと思っていたので実装してみた。 テストちゃんとしてないしもしかしたら間違ってるかも。

こういうのを上げるのって怖い人にいじめられそうで怖いな？笑

//! gcc -o multikeyquicksort.bin multikeyquicksort.c -W -Wall -O3 -std=gnu99 

#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

typedef char * string;

int multikey_qsort( string *strs, int len );
string string_create( char *str );

int main( void )
{
    int len = 5;
    string s[10];
    s[0] = string_create( "ccbb" );
    s[1] = string_create( "ccc"  );
    s[2] = string_create( "zzzzz" );
    s[3] = string_create( "aaaa" );
    s[4] = string_create( "aaa" );
    
    multikey_qsort( s, len );

    for ( int i = 0; i < len; i++ ) {
        printf( "%s\n", s[i] );
    }

    return 0;
}


/*** implementation ***/
string string_create( char *str )
{
    return str;
}

int string_cmp( string s1, string s2, int pos )
{
         if ( s1[pos] > s2[pos] ) return  1;
    else if ( s1[pos] < s2[pos] ) return -1;
    else                          return  0;
}

int string_null( string s, int pos )
{
    return s[pos] == '\0';
}

int _multikey_qsort( string *strs, int len, int pos )
{
    if ( len < 2 ) return 0;
    string  pivot    = strs[0];
    int     nnull    = 0;
    int     nsmaller = 0;
    int     nsame    = 0;
    int     nlarger  = 0;
    string  null   [len];
    string  smaller[len];
    string  same   [len];
    string  larger [len];

    for ( int i = 0; i < len; i++ ) {
        if ( string_null( strs[i], pos ) ) {
            null[nnull++] = strs[i];
            continue;
        }

        int result = string_cmp( strs[i], pivot, pos );
             if ( result < 0 ) smaller[nsmaller++] = strs[i];
        else if ( result > 0 ) larger [nlarger++]  = strs[i];
        else                   same   [nsame++]    = strs[i]; 

    }
    
    int head = 0;
    memcpy( &strs[head], null,    nnull    * sizeof(string) );
    head += nnull;
    memcpy( &strs[head], smaller, nsmaller * sizeof(string) );
    head += nsmaller;
    memcpy( &strs[head], same,    nsame    * sizeof(string) );
    head += nsame;
    memcpy( &strs[head], larger,  nlarger  * sizeof(string) );

    head = nnull;
    _multikey_qsort( &strs[head], nsmaller, pos );
    head += nsmaller;
    _multikey_qsort( &strs[head], nsame   , pos+1 );
    head += nsame;
    _multikey_qsort( &strs[head], nlarger , pos );
    
    return 0;
}

int multikey_qsort( string *strs, int len )
{
    _multikey_qsort( strs, len, 0 );
    return 0;
}