Привет, сегодня поговорим про сортировка строк, обещаю рассказать все что знаю. Для того чтобы лучше понимать что такое сортировка строк, сортировка структур на е языка си , настоятельно рекомендую прочитать все из категории Алгоритмы и теория алгоритмов.

Сортировка других структур данных

До сих пор мы сортировали только массивы символов. Очевидно, что приведенные выше функции можно переделать для сортировки массивов любого из встроенных типов данных, просто поменяв типы параметров и переменных. Тем не менее, обычно возникает необходимость сортировать составные типы данных, например строки, или агрегированные данные, например структуры. Большинство задач сортировки имеют дело с ключом и информацией, связанной с этим ключом. Чтобы адаптировать алгоритмы для обработки подобных данных, необходимо модифицировать код сравнения, код обмена или оба фрагмента. Сам алгоритм при этом не меняется.

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

сортировка строк

Сортировка строк является распространенной задачей программирования. Строки легче всего сортировать, когда они хранятся в таблице строк. Таблица строк — это просто массив строк. А массив строк — это двумерный массив символов, в котором количество строк в таблице определяется размером левого измерения, а максимальная длина строки — размером правого измерения. (О массивах строк рассказывалось в главе 4.) Нижеследующая строковая версия быстрой сортировки принимает массив строк, в котором размер каждой строки ограничен десятью символами. (Можете изменить эту длину, если хотите.) Данная версия сортирует строки в лексикографическом порядке.

    

        
Electron in the transistor-resistor kingdom
        

          Game: Perform tasks and rest cool.6 people play!
        
        
            Play game
        
    
    

          
                   
        

    
/* Быстрая сортировка строк. */
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(). Об этом говорит сайт https://intellect.icu . Эта функция возвращает отрицательное число, если первая строка лексикографически меньше второй, возвращает ноль, если строки равны, и положительное число, если первая строка лексикографически больше второй. Также следует отметить, что для обмена двух строк требуется три вызова функции 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;
}

Сортировка структур

В большинстве прикладных программ, в которых используется сортировка, предусмотрена сортировка совокупностей данных. Например, списки почтовой рассыпки, складские базы данных и журналы сотрудников содержат наборы разнотипных данных. Как вам известно, в программах на языке С совокупности данных обычно хранятся в структурах. Хотя структура обычно содержит несколько членов, структуры, как правило, сортируются только по одному полю-члену, который используется в качестве ключа сортировки. За исключением выбора ключа, приемы сортировки структур ничем не отличаются от приемов сортировки других типов данных.

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

struct address {
  char name[40];   /* имя */
  char street[40]; /* улица */
  char city[20];   /* город */
  char state[3];   /* штат */
  char zip[11];    /* индекс */
};

Поскольку представляется разумным организовать список адресов в виде массива структур, в данном примере предположим, что процедура сортировки будет сортировать массив структур типа address. Такая процедура показана ниже. Она сортирует адреса по почтовому индексу.

    

        
Electron in the transistor-resistor kingdom
        

          Game: Perform tasks and rest cool.6 people play!
        
        
            Play game
        
    
    

          
                   
        

    
/* Быстрая сортировка структур типа фвкуыы. */
void quick_struct(struct address items[], int count)
{
  qs_struct(items,0,count-1);
}

void qs_struct(struct address items[], int left, int right)
{

  register int i, j;
  char *x;
  struct address temp;

  i = left; j = right;
  x = items[(left+right)/2].zip;

  do {
    while((strcmp(items[i].zip,x) < 0) && (i < right)) i++;
    while((strcmp(items[j].zip,x) > 0) && (j > left)) j--;
    if(i <= j) {
      temp = items[i];
      items[i] = items[j];
      items[j] = temp;
      i++; j--;
    }
  } while(i <= j);

  if(left < j) qs_struct(items, left, j);
  if(i < right) qs_struct(items, i, right);
}

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

Из статьи мы узнали кратко, но содержательно про сортировка строк