Ответ 1

Храните похожие слова вместе...

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

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);
}

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

Ответ 2

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

Сначала просмотрите порядок сортировки 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, игнорируя случай (например, то же слово, что и "MILK" и "молоко" ) теперь сравнивает случай и отменяет порядок:

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 collations. Например, в разных местах буквы алфавита отличаются друг от друга:

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 и сравнение строк. Вы можете изменять значения по умолчанию, чтобы фиксировать различие между сортировкой словарей и сортировкой телефонной книги, различными местоположениями или различными способами лечения для случая. Отдельные вариации местоположения активно отслеживаются в репозитории данных Unicode Common Locale (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 Library. Значение по умолчанию для DUCET для нескольких примеров:

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

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

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

Ответ 3

Ключом кода 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(), вы получите желаемый результат.

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

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

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

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

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

Ответ 4

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

Нечувствительная к регистру сортировка, при которой условие тай-брейка "нижний регистр приходит первым" должно использоваться.

Так оно нравится:

• earlier_letter_in_the_alphabet < later_letter_in_the_alphabet игнорируя случай

• lowercase < uppercase

• shorter_word < wider_word
  • Это не упоминалось, я одолжил его в лексикографическом порядке, в словарях
  • Можно использовать, просто взяв '\0' как минимально возможное в сравнении

Шаг 2 будет выполнен только в том случае, если 1 ничего не различал. Шаг 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;
}

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

Ответ 5

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

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

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

#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 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 */

Ответ 6

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

#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;
}