Занятие 7

В языке C для сортировки используется функция, объявляемая в <stdlib.h>

void qsort(void *a, int n, int s, int f(const void *, const void *));

Для сортировки массива из 100 целых чисел эту функцию нужно использовать так:

int icmp(const void *a1, const void *a2)
{ const int *b1, *b2;
  b1=(const int *)a1;
  b2=(const int *)a2;
  if(*b1<*b2) return -1;
  if(*b1>*b2) return 1;
  return 0;
}
int a[100];
...
qsort(a,100,sizeof(a[0]),icmp);

В языке C++ для сортировки используется функция-шаблон, определенная в <algorithm>

void sort(iterator first, iterator last);
void sort(iterator first, iterator last, bool less(...));

Для сортировки массива из 100 целых чисел по возрастанию функция sort вызывается так:

int a[100];
sort(a,a+100);

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

sort(a,a+100,greater<int>()); // в порядке убывания
sort(a,a+100,mcmp); // по модулю значения
...
bool mcmp(int a1, int a2)
{ if(abs(a1)<abs(a2)) return true;
  return false;
}

Стандартная сортировка выполняется за время `O(N\ log\ N)`, но существует сортировка, требующая меньше времени, но использующая дополнительную память. Это "карманная" или "поразрядная" сортировка.

Предположим, нам нужно отсортировать колоду из 52 игральных карт. Одна карта предшествует другой, если либо она младше по масти, либо масти обеих карт одинаковы, но она младше по достоинству. Сначала разложить карты в 13 стопок лицевой стороной вверх по их достоинству. Затем собрать все стопки вместе: снизу тузы, затем двойки, тройки и т. д. и сверху короли (лицевой стороной вверх). Перевернуть колоду рубашками вверх и снова разложить, на этот раз в четыре стопки по масти. Сложив вместе полученные стопки так, чтобы внизу были трефы, затем бубны, черви и пики, получим упорядоченную колоду карт. Почему сортировка правильна? Потому что, если две карты при последнем раскладе попали в разные стопки, то они имеют разные масти, так что карта с меньшей мастью младше. Если же карты одной масти, то они уже находятся в нужном порядке благодаря предварительной сортировке. Иначе говоря, при втором раскладе в каждой из четырех стопок карты будут расположены в возрастающем порядке.

Для реализации необходима дополнительная память для `N` значений и `M` счетчиков. Сначала определяется количество значений в каждой стопке, затем по счетчикам устанавливаются смещения на начало соответствующего кармана (можно использовать массив счетчиков, подсчитав частичные суммы). Далее данные перемещаются по соответствующим карманам, и алгоритм повторяется для следующего разряда ключа.

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