Cортировка строк является распространенной задачей программирования. Строки легче всего сортировать, когда они хранятся в таблице строк. Таблица строк — это просто массив строк. А массив строк — это двумерный
массив символов, в котором количество строк в таблице определяется размером левого измерения, а максимальная длина строки — размером правого измерения. Нижеследующая строковая версия
быстрой сортировки принимает массив строк, в котором размер каждой строки ограничен десятью символами. Данная версия сортирует строки в лексикографиче¬ском порядке.
/* Быстрая сортировка строк. */
void quick_string (char items[][10], int count)
{
qs_string(items, 0, count-1);
}
void qs_string(char items[][10], int left, int right)
{
register int i, j;
char *x;
char temp[10];
i = left; j = right;
x = items [(left+right)/2];
do {
while((strcmp(items[i],x) < 0) && (i < right)) i++;
while (strcmp(items[j] , x) > 0) && (j > left)) j -- ;
if(i <= j) {
strcpy(temp, items[i]);
strcpy(items[i], items[j]);
strcpy(items[j], temp);
i++; j--;
}
} while(i <= j);
if (left < j) qs_string (items, left, j) ;
if(i < right) qs_string(items, i, right);
}
Во фрагменте сравнения теперь используется
функция strcmp(). Эта функция возвращает отрицательное число, если первая строка лексикографически меньше второй, возвращает ноль, если строки равны, и положительное число, если первая строка лексикографически больше второй. Также следует отметить, что для обмена двух строк требуется три вызова
функции strcpy ().
Функция strcmp() замедляет сортировку по двум причинам. Во-первых, в программе появляется вызов функции, что всегда отнимает время. Во-вторых, сама функция strcmp() выполняет несколько сравнений, чтобы определить, какая из двух строк больше. В первом случае, если скорость очень важна, можно поместить код сравнения строк непосредственно в функцию сортировки, продублировав код функции strcmp(). Во втором случае нет никакого способа избежать сравнения строк, поскольку по определению это именно то, что требуется в данной задаче. Те же рассуждения относятся и к функции strcpy(). Обмен двух строк с помошью strcpy() включает в себя вызов функции и посимвольный обмен содержимого строк — каждая из этих операций занимает время. Накладные расходы на вызов функции можно устранить, вставив код копирования прямо в алгоритм сортировки. Однако тот факт, что обмен двух строк означает обмен отдельных символов (один за другим), изменить невозможно.
Ниже приведена простая функция
main() , демонстрирующая работу функции быстрой сортировки строк quick_string ():
#include <stdio.h>
#include <string.h>
void quick_string(char items[] [10], int count);
void qs_string(char items[] [10], int left, int right);
char str[][10] = { "один", "два", "три", "четыре"
};
int main(void)
{
int i;
quick__string(str, 4);
for (i=0; i<4; i++) printf("%s ", str[i]);
return 0;
}