Держите одинаковые слова вместе ...

Для списков слов часто более полезно сгруппировать «одинаковые» слова вместе (даже если они различаются по регистру). Например:

Keeping things together:          Simple "M after m":
------------------------          -------------------
mars                              mars
mars bar                          mars bar
Mars bar                          milk
milk                              milk-duds
Milk                              milky-way
milk-duds                         Mars bar
milky-way                         Milk
Milky-way                         Milky-way

Если вы хотите, чтобы слова были расположены как в первом столбце, я предлагаю три способа сделать это:

• Использование strcasecmp() в сочетании с strcmp().
• Однопроходная реализация, отслеживающая тип символа с помощью isalpha(), tolower() и isupper().
• Однопроходная реализация, использующая таблицу сортировки.

В конце я обсуждаю две альтернативы:

• Использование таблицы сопоставления для создания произвольного порядка.
• Установка языкового стандарта для использования сортировки на основе языкового стандарта.

Использование доступных библиотечных функций

Если это возможно, не изобретайте велосипед. В этом случае мы можем сделать это, используя функцию POSIX strcasecmp(), чтобы проверить, равны ли они, с помощью сравнения без учета регистра, и вернувшись к strcmp(), когда они равны.

int alphaBetize (const char *a, const char *b) {
    int r = strcasecmp(a, b);
    if (r) return r;
    /* if equal ignoring case, use opposite of strcmp() result to get
     * lower before upper */
    return -strcmp(a, b); /* aka: return strcmp(b, a); */
}

(В некоторых системах функция сравнения без учета регистра называется stricmp() или _stricmp(). Если она вам недоступна, ниже представлена ​​реализация.)

#ifdef I_DONT_HAVE_STRCASECMP
int strcasecmp (const char *a, const char *b) {
    while (*a && *b) {
        if (tolower(*a) != tolower(*b)) {
            break;
        }
        ++a;
        ++b;
    }
    return tolower(*a) - tolower(*b);
}
#endif

Избегайте двух проходов по струнам

Иногда существующие функции работают недостаточно хорошо, и вам нужно делать что-то еще, чтобы ускорить работу. Следующая функция выполняет сравнение примерно таким же образом за один проход и без использования strcasecmp() или strcmp(). Но он рассматривает все небуквенные символы как меньшие, чем буквы.

int alphaBetize (const char *a, const char *b) {
    int weight = 0;
    do {
        if (*a != *b) {
            if (!(isalpha(*a) && isalpha(*b))) {
                if (isalpha(*a) || isalpha(*b)) {
                    return isalpha(*a) - isalpha(*b);
                }
                return *a - *b;
            }
            if (tolower(*a) != tolower(*b)) {
                return tolower(*a) - tolower(*b);
            }
            /* treat as equal, but mark the weight if not set */
            if (weight == 0) {
                weight = isupper(*a) - isupper(*b);
            }
        }
        ++a;
        ++b;
    } while (*a && *b);
    /* if the words compared equal, use the weight as tie breaker */
    if (*a == *b) {
        return weight;
    }
    return !*b - !*a;
}

При использовании этого сравнения для сортировки milk и Milk будут оставаться рядом друг с другом, даже если список включает milk-duds.

Использование таблицы сопоставления

Вот способ динамического создания таблицы сортировки из «конфигурации». Он служит для иллюстрации метода сравнения, позволяющего изменить способ сравнения строк.

Вы можете сопоставить, как буквы алфавита сравниваются, с помощью некой простой таблицы, которая описывает относительный порядок букв (или любого символа, кроме байта NUL), который вы хотите иметь:

const char * alphaBetical =
    "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ";

Из этого порядка мы можем создать справочную таблицу, чтобы увидеть, как две буквы должны сравниваться друг с другом. Следующая функция инициализирует таблицу, если это еще не было сделано, в противном случае выполняет поиск в таблице.

int alphaBeta_lookup (int c) {
    static int initialized;
    static char table[CHAR_MAX+1];
    if (!initialized) {
        /* leave all non-alphaBeticals in their relative order, but below
           alphaBeticals */
        int i, j;
        for (i = j = 1; i < CHAR_MAX+1; ++i) {
            if (strchr(alphaBetical, i)) continue;
            table[i] = j++;
        }
        /* now run through the alphaBeticals */
        for (i = 0; alphaBetical[i]; ++i) {
            table[(int)alphaBetical[i]] = j++;
        }
        initialized = 1;
    }
    /* return the computed ordinal of the provided character */
    if (c < 0 || c > CHAR_MAX) return c;
    return table[c];
}

С помощью этой справочной таблицы мы теперь можем упростить тело цикла функции сравнения alphaBetize():

int alphaBetize (const char *a, const char *b) {
    int ax = alphaBeta_lookup(*a);
    int bx = alphaBeta_lookup(*b);
    int weight = 0;
    do {
        char al = tolower(*a);
        char bl = tolower(*b);
        if (ax != bx) {
            if (al != bl) {
                return alphaBeta_lookup(al) - alphaBeta_lookup(bl);
            }
            if (weight == 0) {
                weight = ax - bx;
            }
        }
        ax = alphaBeta_lookup(*++a);
        bx = alphaBeta_lookup(*++b);
    } while (ax && bx);
    /* if the words compared equal, use the weight as tie breaker */
    return (ax != bx) ? !bx - !ax : weight;
}

Можем ли мы сделать вещи проще?

Используя таблицу сопоставления, вы можете создавать множество различных порядков с помощью упрощенной функции сравнения, например:

int simple_collating (const char *a, const char *b) {
    while (alphaBeta_lookup(*a) == alphaBeta_lookup(*b)) {
        if (*a == '\0') break;
        ++a, ++b;
    }
    return alphaBeta_lookup(*a) - alphaBeta_lookup(*b);
}

Используя ту же функцию и изменяя строку alphaBetical, вы можете добиться почти любого нужного вам порядка (алфавитный, обратный алфавитный, гласные перед согласными и т. Д.). Однако расположение одинаковых слов вместе требует перемежения слов с заглавной буквы и слов в нижнем регистре, и это можно сделать только путем сравнения без учета регистра.

Обратите внимание, что с функцией simple_collating() и указанной мною alphaBetical строкой Bacon будет стоять перед milk, но Mars будет идти после milk и перед Milk.

Если вы хотите отсортировать по вашему языку.

Если вы хотите использовать последовательность сортировки, которая уже определена для вашего языкового стандарта, вы можете установить языковой стандарт и вызвать функцию сравнения сопоставления:

/*
 * To change the collating locale, use (for example):
       setlocale(LC_COLLATE, "en.US");
 */
int iso_collating (const char *a, const char *b) {
    return strcoll(a, b);
}

Теперь, изменив языковой стандарт, порядок сортировки будет основан на стандартизированной последовательности сортировки.

Вы можете написать собственную функцию сравнения для сортировки.

Сначала посмотрите на strcmp порядок сортировки по умолчанию:

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

const char *tgt[]={
    "bacon", "Bacon", "mIlk", "Milk", "spinach", "MILK", "milk", "eggs"
};
int tgt_size=8;

static int cmp(const void *p1, const void *p2){
    return strcmp(* (char * const *) p1, * (char * const *) p2);
}

int main(int argc, char *argv[]) {
    printf("Before sort:\n\t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    qsort(tgt, tgt_size, sizeof(char *), cmp);

    printf("\nAfter sort:\n\t");
    for(int n=0; n<tgt_size; n++)
        printf("%s ", tgt[n]);

    return 0;
}

strcmp сортирует по коду символа ASCII; т.е. он сортирует A-Z, затем a-z, поэтому все заглавные A-Z идут перед любым словом с строчной буквой:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    Bacon MILK Milk bacon eggs mIlk milk spinach 

Мы можем написать нашу собственную функцию сравнения, используемую в cmp, используемую в qsort, которая игнорирует регистр. Это выглядит так:

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == '\0')
            return 0;
    return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);
} 

Не забудьте также изменить cmp на:

static int cmp(const void *p1, const void *p2){
    return mycmp(* (char * const *) p1, * (char * const *) p2);
}

Версия, игнорирующая регистр, теперь печатает:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs Milk MILK milk mIlk spinach 

Это тот же результат, который вы получите с функцией POSIX strcasecmp.

Функция mycmp сначала выполняет лексикографическое сравнение в нормальном порядке [a|A]-[z|Z]. Это означает, что вы получите вместе слова из одинаковых букв, но вы можете получить bacon, Bacon с такой же вероятностью, как и Bacon, bacon. Это связано с тем, что qsort не является стабильной сортировкой и «Бекон» сравнивается с «беконом». .

Теперь мы хотим, чтобы сравнение было равно 0, игнорируя регистр (то есть такое же слово, как «МОЛОКО» и «молоко»), теперь сравниваем, включая регистр, и меняем порядок:

int mycmp(const char *a, const char *b) {
    const char *cp1 = a, *cp2 = b;
    int sccmp=1;

    for (; toupper(*cp1) == toupper(*cp2); cp1++, cp2++)
        if (*cp1 == '\0')
            sccmp = 0;
    if (sccmp) return ((toupper(*cp1) < toupper(*cp2)) ? -1 : +1);

    for (; *a == *b; a++, b++)
        if (*a == '\0')
            return 0;
    return ((*a < *b) ? +1 : -1);
}

Окончательная версия распечатывает:

Before sort:
    bacon Bacon mIlk Milk spinach MILK milk eggs 
After sort:
    bacon Bacon eggs milk mIlk Milk MILK spinach 

К сожалению, для UNICODE такой подход становится громоздким. Для сложных сортировок рассмотрите возможность использования сопоставления или многоэтапной сортировки с стабильной сортировкой.

Для сложных сортировок по алфавиту с учетом местоположения рассмотрите сопоставления Unicode. Например, в разных местах буквы расположены по-разному:

Swedish                      z < ö
                             y == w
German                       ö < z
Danish                       Z < Å
Lithuanian                   i < y < k
Tr German                    ä == æ
Tr Spanish                   c < ch < d   
German Dictionary Sort:      of < öf
German Phonebook Sort:       öf < of

Значения по умолчанию для этих различий фиксируются в таблице элементов сопоставления Unicode по умолчанию (DUCET), который обеспечивает сопоставление по умолчанию для параметров сортировки UNICODE и сравнения строк. Вы можете изменить значения по умолчанию, чтобы уловить различие между сортировкой словаря и сортировкой телефонной книги, разными местоположениями или различным подходом к регистру. Индивидуальные варианты местоположения активно отслеживаются в репозитории данных Common Locale Unicode (CLDR).

Рекомендации для многоуровневой сортировки являются многоуровневыми:

Level   Description           Examples
L1      Base characters       role < roles < rule
L2      Accents               role < rôle < roles
L3      Case/Variants         role < Role < rôle
L4      Punctuation           role < “role” < Role
Ln      Identical             role < ro□le < “role”

Широко используемая реализация сопоставления Unicode находится в библиотеке ICU. Параметры сортировки DUCET по умолчанию для нескольких примеров будут такими:

b < B < bad < Bad < bäd
c < C < cote < coté < côte < côté 

Вы можете изучить библиотеку ICU и изменить местоположения и цели с помощью ICU Explorer

Если вы хотите реализовать свою собственную версию DUCET для хихиканья, вы можете следовать общему методу, используемому в этом скрипт Python. Это не ошеломляюще, но и нетривиально.

Ключевым моментом кода OP является использование функции strcmp() для сравнения двух строк.
Итак, я начну с замены этой стандартной функции другой, например следующей:

  // We assume that the collating sequence satisfies the following rules:
  // 'A' < 'B' < 'C' < ...
  // 'a' < 'b' < 'c' < ...
  // We don't make any other assumptions.

  #include <ctype.h>      
  int my_strcmp(const char * s1, const char * s2)
  {
      const char *p1 = s1, *p2 = s2;
      while(*p1 == *p2 && *p1 != '\0' && *p2 != '\0')
          p1++, p2++;  /* keep searching... */

      if (*p1 == *p2)
         return 0;
      if (*p1 == '\0')
         return -1;
      if (*p2 == '\0')
         return +1;

      char c1 = tolower(*p1),      c2 = tolower(*p2);
      int  u1 = isupper(*p1) != 0, u2 = isupper(*p2) != 0;
      if (c1 != c2)
        return c1 - c2;  // <<--- Alphabetical order assumption is used here 
      if (c1 == c2)
        return u1 - u2;
  }

Последние строчки можно уплотнить таким образом:

     return (c1 != c2)? c1 - c2: u1 - u2;

Теперь, заменив strcmp() на my_strcmp(), вы получите желаемый результат.

В алгоритме сортировки рекомендуется отдельно продумать 3 его основных аспекта:

• Функция сравнения.
• Алгоритм абстрактной сортировки, который мы будем использовать.
• Способ, которым данные будут «перемещены» в массиве, когда нужно поменять местами два элемента.

Эти аспекты можно оптимизировать независимо.
Таким образом, например, после того, как вы правильно настроили функцию сравнения, следующим шагом оптимизации может быть замена алгоритма сортировки double for на более эффективный, например, quicksort.
В частности, функция qsort() стандартной библиотеки <stdlib.h> предоставляет вам такой алгоритм, поэтому вам не нужно беспокоиться о его программировании.
Наконец, стратегия вы используете для хранения информации о массиве, это может иметь последствия для производительности.
Было бы более эффективно хранить такие строки, как «массив указателей на char», а не «массив из массива char», поскольку замена указателей выполняется быстрее, чем замена двух целые массивы символов.

Массивы указателей

ДОПОЛНИТЕЛЬНОЕ ПРИМЕЧАНИЕ. Три первых if() на самом деле избыточны, потому что логика следующих предложений подразумевает желаемый результат в случае, если *p1 или *p2 равно 0. Однако, сохраняя эти if(), код становится больше удобочитаемый.

Здесь, если я понял, вам нужно что-то, как я бы описал следующим образом:

Сортировка без учета регистра, при которой в качестве условия разрешения конфликтов "нижний регистр идет впереди" должно использоваться условие.

Так это как:

1. earlier_letter_in_the_alphabet < later_letter_in_the_alphabet без учета регистра

2. lowercase < uppercase

3. shorter_word < wider_word
   • This wasn't mentioned, I borrowed it from the lexicographical order, the one in dictionaries
   • Можно использовать, просто взяв '\0' как наименьшее возможное при сравнении.

Шаг 2 следует выполнять только в том случае, если я ничего не различил. Шаг 3 уже будет проверяться с помощью 1. Все это должно выполняться по буквам, а это означает, что вы должны переключиться на 2, как только вы получите связь между соответствующими символами, а не только тогда, когда все строки связаны.

Предполагая, что это было правильно, все, что нам нужно сделать сейчас, это написать функцию, которая выполняет это сравнение за нас для любых данных двух строк.

#include <ctype.h>  // for tolower and islower

int my_character_compare(const char a, const char b)
{
    int my_result;

    my_result = tolower(a) - tolower(b);
    // unless it is zero, my_result is definitely the result here
    // Note: if any one of them was 0, result will also properly favour that one


    if (my_result == 0 && a != b)
    // if (could not be distinguished with #1, but are different)
    {
        // means that they are case-insensitively same
        // but different...
        // means that one of them are lowercase, the other one is upper
        if (islower(a))
            return -1;  // favour a
        else
            return 1;   // favour b
    }


    // regardless if zero or not, my_result is definitely just the result
    return my_result;
}

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    my_result = my_character_compare(*a, *b);
    // unless it is zero, my_result is definitely the result here

    while (my_result == 0 && *a != 0)
    // current characters deemed to be same
    // if they are not both just 0 we will have to check the next ones
    {
        my_result = my_character_compare(*++a, *++b);
    }

    // whatever the my_result has been:
    //   whether it became != zero on the way and broke out of the loop
    //   or it is still zero, but we have also reached the end of the road/strings
    return my_result;
}

Функция сравнения, по соглашению / правилу, должна возвращать отрицательное значение для предпочтения первого параметра впереди, отрицательное значение для предпочтения второго параметра и ноль, если она не может их различить. Просто дополнительная информация, которую вы, вероятно, уже знаете по тому, как вы используете strcmp.

Вот и все! Замена этого strcmp в вашем коде на my_string_compare здесь, а также размещение этих определений, которые мы сделали, должны дать правильный результат. Действительно, он обеспечивает ожидаемый результат для рассматриваемого примера ввода.

Конечно, можно было бы сократить определения, я сделал их длинными, чтобы было легче понять, что происходит. Например, я мог бы свести все к следующему:

#include <ctype.h>

int my_string_compare(const char * a, const char * b)
{
    int my_result;

    while (*a || *b)
    {
        if ((my_result = tolower(*a) - tolower(*b)))
            return my_result;
        if (*a != *b)
            return (islower(*a)) ? -1 : 1;
        a++;
        b++;
    }

    return 0;
}

По сути, делает то же самое с другим, вы можете использовать то, что вам нравится; или даже лучше, напишите один.

Я опаздываю на это обсуждение и не особо ожидаю, что пойду и возьму невероятный приз, но, не видя решения, использующего идиомы, на которые я сначала обратил внимание, подумал, что вмешаюсь.

Моей первой мыслью при чтении спецификации проблемы была некоторая форма настраиваемой последовательности сортировки, которую я в основном нашел в понятии Использование таблицы сопоставления @ jxh. Я не считаю нечувствительность к регистру ключевой концепцией, а просто странный порядок.

Итак, я предлагаю следующий код исключительно в качестве альтернативной реализации. Он специфичен для glibc - используется qsort_r (3) - но кажется более легким подходом и поддерживает множество последовательностей сортировки во время выполнения. Но он прошел легкие испытания, и я, скорее всего, упускаю различные слабые места. Среди них: я не уделял особого внимания Unicode или миру широких символов в целом, и приведение к беззнаковым символам, чтобы избежать отрицательных индексов массива, вызывает подозрение.

#include <stdio.h>
#include <limits.h>

/*
 * Initialize an index array associated with the collating
 * sequence in co. The affected array can subsequently be
 * passed in as the final client data pointer into qsort_r
 * to be used by collating_compare below.
 */
int
collating_init(const char *co, int *cv, size_t n)
{
    const unsigned char *uco = (const unsigned char *) co;
    const unsigned char *s;
    size_t i;

    if (n <= UCHAR_MAX) {
        return -1;
    }
    for (i = 0; i < n; i++) {
        /* default for chars not named in the sequence */
        cv[i] = UCHAR_MAX;
    }
    for (s = uco; *s; s++) {
        /*
         * the "collating value" for a character's own
         * character code is its ordinal (starting from
         * zero) in the collating sequence. I.e., we
         * compare the values of cv['a'] and cv['A'] -
         * rather than 'a' and 'A' - to determine order.
         */
        cv[*s] = (s - uco);
    }

    return 0;
}

static int
_collating_compare(const char *str1, const char *str2, int *ip)
{
    const unsigned char *s1 = (const unsigned char *) str1;
    const unsigned char *s2 = (const unsigned char *) str2;

    while (*s1 != '\0' && *s2 != '\0') {
        int cv1 = ip[*s1++];
        int cv2 = ip[*s2++];

        if (cv1 < cv2) return -1;
        if (cv1 > cv2) return 1;
    }

    if (*s1 == '\0' && *s2 == '\0') {
        return 0;
    } else {
        return *s1 == '\0' ? -1 : 1;
    }
}

int
collating_compare(const void *v1, const void *v2, void *p)
{
    return _collating_compare(*(const char **) v1,
                              *(const char **) v2,
                              (int *) p);
}

Предыдущий пример близок к коду, который можно было бы поместить в отдельный модуль или библиотеку, но в нем отсутствует собственный файл заголовка (или запись в файле заголовка). Мой собственный тест просто объединяет приведенный выше и ниже код в файл с именем custom_collate_sort.c и использует

gcc -DMAIN_TEST -Wall -o custom_collate_sort custom_collate_sort.c

... скомпилировать его.

#if defined(MAIN_TEST)

/* qsort_r is a GNU-ey thing... */

#define __USE_GNU
#include <stdlib.h>
#include <string.h>

#define NELEM(x) (sizeof x / sizeof 0[x])

static int
cmp(const void *v1, const void *v2)
{
    return strcmp(*(const char **) v1, *(const char **) v2);
}

static int
casecmp(const void *v1, const void *v2)
{
    return strcasecmp(*(const char **) v1, *(const char **) v2);
}

int
main(int ac, char *av[])
{
    size_t i;

    int cval[256], ret;
    int cval_rev[256], rret;

    char *tosort[] = {
        "cheeSE", "eggs", "Milk", "potatoes", "cheese", "spaghetti",
        "eggs", "milk", "spinach", "bacon", "egg", "apple", "PEAR",
        "pea", "berry"
    };

    ret = collating_init("aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVxXyYzZ",
                         cval, NELEM(cval));

    rret = collating_init("ZzYyXxVvUuTtSsRrQqPpOoNnMmLlKkJjIiHhGgFfEeDdCcBbAa",
                          cval_rev, NELEM(cval_rev));

    if (ret == -1 || rret == -1) {
        fputs("collating value array must accomodate an index of UCHAR_MAX\n", stderr);
        return 1;
    }

    puts("Unsorted:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], cmp);

    puts("Sorted w/ strcmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort((void *) tosort, NELEM(tosort), sizeof tosort[0], casecmp);

    puts("Sorted w/ strcasecmp:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval);

    puts("Sorted w/ collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    qsort_r((void *) tosort, NELEM(tosort), sizeof tosort[0],
            collating_compare, (void *) cval_rev);

    puts("Sorted w/ reversed collating sequence:");
    for (i = 0; i < NELEM(tosort); i++) {
        printf("  %s\n", tosort[i]);
    }

    return 0;
}

#endif /* MAIN_TEST */

Стандартные файлы заголовков, необходимые для программы:

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

Основная программа начинается здесь:

//Global Variables Required
//=========
const char *tgt[]={"bacon", "Bacon", "mIlk", 
        "Milk", "spinach", "MILK", "milk", "eggs"};    //Array for sorting
int tgt_size=8;                                        //Total Number of Records
int     SortLookupTable[128];                          //Custom sorting table
typedef int      cmp_t (const void *, const void *);




int main(int argc, char *argv[]) {
    printf("Before sort:\n\n");
    int n=0;
    for(n=0; n<tgt_size; n++)
        printf("%s\n", tgt[n]);

    CreateSortTable();

    myQsort(tgt, tgt_size, sizeof(char *), &compare);
    printf("\n\n====\n\n");
    for(n=0; n<tgt_size; n++)
        printf("%s\n", tgt[n]);

    return 0;
}

Настраиваемая таблица сортировки по мере необходимости:

void CreateSortTable(void){
    int     i;
    for (i = 0; i < 128; i++){
        SortLookupTable[i] = 0;
    }
    char *s;
    s=(char *)malloc(64);
    memset(s, 0, 64);
    strcpy(s, "aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ");

    i=1;
    for (; *s; s++){
        SortLookupTable[(int) ((unsigned char) *s)]=i;
        i++;
    }
}

Алгоритм быстрой сортировки, вы также можете использовать предоставленную стандартную библиотеку:

//Some important Definations required by Quick Sort
=======
#define SWAPINIT(a, es) swaptype = ((char *)a - (char *)0) % sizeof(long) || \
    es % sizeof(long) ? 2 : es == sizeof(long)? 0 : 1;

#define swap(a, b)                          \
    if (swaptype == 0) {                    \
        long t = *(long *)(a);              \
        *(long *)(a) = *(long *)(b);        \
        *(long *)(b) = t;                   \
    } else                                  \
        swapfunc(a, b, es, swaptype)

#define vecswap(a, b, n)    if ((n) > 0) swapfunc(a, b, n, swaptype)


#define swapcode(TYPE, parmi, parmj, n) {       \
    long i = (n) / sizeof (TYPE);               \
    register TYPE *pi = (TYPE *) (parmi);       \
    register TYPE *pj = (TYPE *) (parmj);       \
    do {                                        \
        register TYPE   t = *pi;                \
        *pi++ = *pj;                            \
        *pj++ = t;                              \
        } while (--i > 0);                      \
}

#define min(a, b)   (a) < (b) ? a : b


//Other important function
void swapfunc(char *a, char *b, int n, int swaptype){
    if(swaptype <= 1)
        swapcode(long, a, b, n)
    else
        swapcode(char, a, b, n)
}

char * med3(char *a, char *b, char *c, cmp_t *cmp){
    if ( cmp(a, b) < 0){
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){

                return c;
            }else{
                return a;
            }
        }
    }else{
        if (cmp(b, c) < 0){
            return b;
        }else{
            if ( cmp(a, c) < 0){
                return a;
            }else{
                return c;
            }
        }
    }
}

//Custom Quick Sort

void myQsort(void *a, unsigned int n, unsigned int es, cmp_t *cmp){
    char *pa, *pb, *pc, *pd, *pl, *pm, *pn;
    int d, r, swaptype, swap_cnt;

loop:   SWAPINIT(a, es);
    swap_cnt = 0;
    if (n < 7) {
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0; pl -= es){
                swap(pl, pl - es);
            }
        return;
    }
    pm = (char *)a + (n / 2) * es;
    if (n > 7) {
        pl = a;
        pn = (char *)a + (n - 1) * es;
        if (n > 40) {
            d = (n / 8) * es;
            pl = med3(pl, pl + d, pl + 2 * d, cmp);
            pm = med3(pm - d, pm, pm + d, cmp);
            pn = med3(pn - 2 * d, pn - d, pn, cmp);
        }
        pm = med3(pl, pm, pn, cmp);
    }
    swap(a, pm);
    pa = pb = (char *)a + es;

    pc = pd = (char *)a + (n - 1) * es;
    for (;;) {
        while (pb <= pc && (r = cmp(pb, a)) <= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pa, pb);
                pa += es;
            }
            pb += es;
        }
        while (pb <= pc && (r = cmp(pc, a)) >= 0) {
            if (r == 0) {
                swap_cnt = 1;
                swap(pc, pd);
                pd -= es;
            }
            pc -= es;
        }
        if (pb > pc)
            break;
        swap(pb, pc);
        swap_cnt = 1;
        pb += es;
        pc -= es;
    }
    if (swap_cnt == 0) {  /* Switch to insertion sort */
        for (pm = (char *)a + es; pm < (char *)a + n * es; pm += es)
            for (pl = pm; pl > (char *)a && cmp(pl - es, pl) > 0;
                 pl -= es)
                swap(pl, pl - es);
        return;
    }

    pn = (char *)a + n * es;
    r = min(pa - (char *)a, pb - pa);
    vecswap(a, pb - r, r);
    r = min(pd - pc, pn - pd - es);
    vecswap(pb, pn - r, r);
    if ((r = pb - pa) > es)
        myQsort(a, r / es, es, cmp);
    if ((r = pd - pc) > es) {
        /* Iterate rather than recurse to save stack space */
        a = pn - r;
        n = r / es;
        goto loop;
    }
}

Две из наиболее важных функций:

unsigned char Change(char a){
    return (unsigned char ) SortLookupTable[(int)a];
}


int compare (const void *a, const void *b){
    char *s1= *(char **)a;
    char *s2= *(char **)b;
    int ret, len, i;
    ret=0;

    if (strlen((void*)s1) > strlen((void*)s2)){
        len=strlen((void*)s1);
    }else{
        len=strlen((void*)s2) ;
    }

    for(i=0; i<len; i++){
        if ( s1[i] != s2[i]){
            if ( Change(s1[i]) < Change(s2[i]) ){
                ret=0;
                break;
            }else{
                ret=1;
                break;
            }
        }
    }

    return ret;
}