Сортировка строк по их смыслу. (Алгоритм сортировки строк не по алфавиту.)

[begin2009]

Пишу программу для первичного воинского учета. Для понимания дальнейшего кода - данные во время выполнения хранятся в сетке StringGrid, которая у меня называется MainGrid. Необходимо рассортировать записи по воинским званиям. Т.е. "рядовой", "ефрейтор", ...., "верховный главнокомандующий". Пока написана заглушка из быдлокода. Функция ранжирования по званиям (методом "грубой силы"):

Код: Выделить всё

function rang(s: string): integer;
var i: integer;
begin
 s:=WideUpperCase(s);
 if copy(s,1,6)='ГВ. ' then  s:=copy(s,7,length(s));
 i:=666;
 if s='РЯДОВОЙ' then i:=1;
 if s='РЯДОВАЯ' then i:=1;
 if s='МАТРОС' then i:=1;
 if s='ЕФРЕЙТОР' then i:=2;
 if s='МЛ. СЕРЖАНТ' then i:=3;
 if s='СЕРЖАНТ' then i:=4;
 if s='СТ. СЕРЖАНТ' then i:=5;
 if s='СТАРШИНА' then i:=6;
 if s='ПРАПОРЩИК' then i:=7;
 if s='МИЧМАН' then i:=7;
 if s='МЛ. ЛЕЙТЕНАНТ' then i:=8;
 if s='ЛЕЙТЕНАНТ' then i:=9;
 if s='СТ. ЛЕЙТЕНАНТ' then i:=10;
 if s='КАПИТАН' then i:=11;
 rang:=i;
end;

А в самой программе сравниваю:

Код: Выделить всё

  if rang(MainGrid.Cells[4, j+1])<rang(MainGrid.Cells[4, j]) then
    begin
     // вот тут и меняю строки в сетке!
    end;

Помогите, люди добрые, чем сможете! Алгоритм, код на любом языке, идею - как реализовать это по-человечески. Крутится в голове что-то про константу - массив строк и ссылки, но в коде не вытанцовывается. Сам проект на лазаре, но если знаете алгоритм на любом языке (не средствами самого языка - в C# строки даже в свитч можно запузырить), киньте. Люди мы не гордые, переведем.

[smaharbA]

не просче в базе и добавить ид/вес ?

[Bizdelnick]

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

[RasenHerz]

Могу посоветовать каждую строку таблицы хранить в отдельной структуре вроде этой:

Код: Выделить всё

struct Row{
   string id;
   /**
     Другие данные
   */
   unsigned weight;
};

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

P.S. В Qt активно используют Model-View подход (отделяют данные от их представления), что крайне удобно. Если хотите, я напишу вам небольшой пример на C++/Qt

[nadge]

Я так понял, это в какой-то базе хранится? Что если там хранить только числовые идентификаторы (которые Вы высчитываете в приведенном примере), а словесное их значение подставлять уже по мере надобности при визуальном отображении в интерфейсе программы?

Это позволит избежать возможных опечаток, да и код упростит.

[NickLion]

Для ускорения работы со строками могу предложить хэш-таблицу. (Не знаю, есть ли это в паскале/лазарусе)
Пример на C#:

Код: Выделить всё

            var dic = new Dictionary< string, int > () {
                { "РЯДОВОЙ", 1 },
                { "РЯДОВАЯ", 1 },
                { "МАТРОС", 1 },
                { "ЕФРЕЙТОР", 2 },
                { "МЛ. СЕРЖАНТ", 3 },
                { "СЕРЖАНТ", 4 },
                { "СТ. СЕРЖАНТ", 5 },
                { "СТАРШИНА", 6 },
                { "ПРАПОРЩИК", 7 },
                { "МИЧМАН", 7 },
                { "МЛ. ЛЕЙТЕНАНТ", 8 },
                { "ЛЕЙТЕНАНТ", 9 },
                { "СТ. ЛЕЙТЕНАНТ", 10 },
                { "КАПИТАН", 11 },
            };
            string st = "СТАРШИНА";
            int range = 666;
            if( dic.ContainsKey( st ) )
                range = dic[ st ];
            Console.WriteLine( "{0}: {1}", st, range );

На C++ (есть и hash_map, но оно стандартом не является, вроде... или я его готовить не умею):

Код: Выделить всё

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

int main(int argc, char *argv[])
{
    std::map< std::string, int > hm;
    hm[ "РЯДОВОЙ" ] = 1;
    hm[ "РЯДОВАЯ" ] = 1;
    hm[ "МАТРОС" ] = 1;
    hm[ "ЕФРЕЙТОР" ] = 2;
    hm[ "МЛ. СЕРЖАНТ" ] = 3;
    hm[ "СЕРЖАНТ" ] = 4;
    hm[ "СТ. СЕРЖАНТ" ] = 5;
    hm[ "СТАРШИНА" ] = 6;
    hm[ "ПРАПОРЩИК" ] = 7;
    hm[ "МИЧМАН" ] = 7;
    hm[ "МЛ. ЛЕЙТЕНАНТ" ] = 8;
    hm[ "ЛЕЙТЕНАНТ" ] = 9;
    hm[ "СТ. ЛЕЙТЕНАНТ" ] = 10;
    hm[ "КАПИТАН" ] = 11;
    std::string st = "ПРАПОРЩИК";
    std::map< std::string, int >::iterator it = hm.find( st );
    int range = 666;
    if( it != hm.end() )
        range = it->second;
    printf( "%s: %d\n", st.data(), range );
    return 0;
}

[smaharbA]

Так понимаю все считают, что звания/сущности не меняются никогда и хранить их нужно в коде ?

[drBatty]

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

в паскале нет нормальной работы со связанными списками и сложными структурами данных. потому и не вытанцовывается :(

Я так понял, это в какой-то базе хранится? Что если там хранить только числовые идентификаторы (которые Вы высчитываете в приведенном примере), а словесное их значение подставлять уже по мере надобности при визуальном отображении в интерфейсе программы?

Это позволит избежать возможных опечаток, да и код упростит.

безусловно. только проблема в том, что у прапорщика и мичмана ID == 7, т.к. это одно и то-же. что делать с этим?
(не, я-то могу дать с пяток решений, но не знаю, что больше понравится ТС)

ЗЫЖ по теме: самый простой вариант -
создаём массив обычных строк, и потом его сортируем (как массив обычных строк)
"001 РЯДОВОЙ"
"002 ЕФРЕЙТОР"
и т.д.
всегда можно отрезать первые 3 символа, или все символы кроме первых 4х.
ведущие нули необходимы потому, что 100 меньше 2х, если сортировать по алфавиту.

[nadge]

безусловно. только проблема в том, что у прапорщика и мичмана ID == 7, т.к. это одно и то-же. что делать с этим?
(не, я-то могу дать с пяток решений, но не знаю, что больше понравится ТС)

Приписать например 7.1 и 7.2, при сортировке использовать только целую часть, а дробную - при выводе на экран. А так и правда можно дать несколько решений.


Кстати, а чем плох изначальный вариант? Он же вроде работает?

[jobfox]

ООП выучи.

[RasenHerz]

ООП выучи.

А без "умных" фраз ну никак?

[nadge]

Кстати, про ООП. Есть вариант не писать отдельную ф-цию сортировки, а перегрузить ф-цию, используемую классом, выводящим информацию. Т.е. наследовать класс отисходного и там эту свою ф-цию прописать.

[strephil]

Кстати, а чем плох изначальный вариант? Он же вроде работает?

Поддержу вопрос.
Все более сложные решение — использование разного типа ассоцииатвных массвов, хэш-таблиц, автоматов для разбора строк — были бы оправданы в двух случаях:
1) строк очень много, и примитивный алгоритм даёт существенную задержку по времени (все эти лишние сравнения);
2) большое количество строк делает код огромным и трудно управляемым в случае возможных измений.

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

[Crazy]

Н.Вирт "Алгоритмы и структуры данных". Алгоритмы описаны на паскале. Выбирай какой больше нравится.

P.S.
А чем оператор case не нравится?

[drBatty]

Все более сложные решение — использование разного типа ассоцииатвных массвов, хэш-таблиц, автоматов для разбора строк — были бы оправданы в двух случаях:

неудобно будет менять значения в этом списке на 8 листов.
if(s == 'fjfjdjfjkdirjvnj') i = 6;
....
и так много-много.
будет проще организовать это в в виде текстового файла (например в моём формате), и загрузить его при первом старте функции.
как-то так..

[strephil]

drBatty, да с этим-то я и не спорю. но вот хэш-таблицы — это уже, ИМХО, в данно вопросе лишнее. Ясности в код они не добавят.

[drBatty]

да с этим-то я и не спорю. но вот хэш-таблицы — это уже, ИМХО, в данно вопросе лишнее. Ясности в код они не добавят.

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

[begin2009]

Варианты со структурами и приплюсовыванием к строке начала по которому сортировка и пойдет не получаются потому что сами записи при работе я храню в сетке StringGrid. Т.е. программа работает с отображенными в сетке строками. (Люблю всюду совать сетку и XML). Т.е. идеи про ид, массива позиций, связанного списка, хэш-таблицы и т.д. неприменимы. В общем представьте идею программы. Имеется на форме сетка. Загружаем данные. Они записываются в строках и столбцах. Во время работы оперируем содержимым сетки. Перед окончанием сохраняем в xml файл. В других случаях этот подход эффективный, пока не столкнулся с необходимостью сортировать не по алфавиту. Я вот этим подходом от всего предложенного и убегал.
"звания/сущности" в принципе кошерней хранить где-нибудь (хоть в каком-нибудь файле), но надеюсь, что новых званий в стране введено не будет. К тому же убежден, (ну это не программирование а опыт работы) что и выше капитана не будет использовано. Поэтому можно хранить и в коде. Но вот о подсказке drBatty все же подумаю. А действительно, не завоять ли xml-ку и не там ли писать соответствия. Чем в нашей стране черт не шутит? А вдруг завтра введут звание унтершарфюрера? (не дай бог) Про перегрузку и ООП шутку юмора оценил, но беда в том что сортировку производит моя же процедура и перегружать ее мне же (хоть бы и указанным быдлокодом). Базовый класс здесь Grids у которого нет метода сортировки.
Оператор case нравится, но со строками работает только в шарпе. В паскале ни бог мой. Только перечисляемые типы (кста и в си, си++, жабе).

ЗЫ если других идей не появится, разовью свою (может быть с загрузкой пар значений из файла при старте). Я пока тестировал на сотне записей - сортировка на глаз не видна. Завтра сварганю какой-нибудь тестовый файл на несколько тысяч записей. Будет тормозить - подумаю и отпишусь.
ЗЗЫ Ответил всем и сразу. Спасибо за участие.

[NickLion]

А в чём неприменимость хэшей? Тот код, что я привёл просто подставляем в функцию, которую Вы в первом посте привели. Время уменьшается (если инициализацию один раз провести), суть остаётся на месте. А вообще, если некритично и работает - не трогай

[drBatty]

А в чём неприменимость хэшей? Тот код, что я привёл просто подставляем в функцию, которую Вы в первом посте привели. Время уменьшается (если инициализацию один раз провести), суть остаётся на месте. А вообще, если некритично и работает - не трогай

вместо чисел (прапорщик == 7) вы возьмёте хеши? ну и что дальше? ведь это ключи для сортировки. какой смысл сортировать по случайно разбросанным ключам? разве что для того, что-бы внести хаос.

[NickLion]

А в чём неприменимость хэшей? Тот код, что я привёл просто подставляем в функцию, которую Вы в первом посте привели. Время уменьшается (если инициализацию один раз провести), суть остаётся на месте. А вообще, если некритично и работает - не трогай

вместо чисел (прапорщик == 7) вы возьмёте хеши? ну и что дальше? ведь это ключи для сортировки. какой смысл сортировать по случайно разбросанным ключам? разве что для того, что-бы внести хаос.

Упс, я имел в виду хэш-таблицу. Не хэш-значение. Ну, код я выше постил.

[begin2009]

Родилась мысль. А строка типа "01рядовой02ефрейтор03мл. сержант......." и функция pos(). Бегу реализовывать.

[drBatty]

Упс, я имел в виду хэш-таблицу. Не хэш-значение. Ну, код я выше постил.

а.. понял.

Родилась мысль. А строка типа "01рядовой02ефрейтор03мл. сержант......." и функция pos(). Бегу реализовывать.

вроде была search? в php например? или у вас pos тоже ищет?

[Crazy]

Загружаем данные. Они записываются в строках и столбцах. Во время работы оперируем содержимым сетки.

Прямой доступ к элементам сетки есть, значит можно применить алгоритм сортировки Хоара("быстрая" сортировка).
Сами алгоритмы сортировки не зависят от типа данных, которые они сортируют. Обычно в стиле STL пишут функцию
сравнения двух элементов сортируемого множества. Эта функция может использовать то отображения сортируемого множества, на множество натуральных чисел, которое вы предложили вначале.
Если не нравится конструкции if ... then, то можно использовать хеш, как структуру с постоянным времени доступа, в котором элемент сортируемого множества является ключом к своему отображению на пространство натуральных чисел.

[begin2009]

вроде была search? в php например? или у вас pos тоже ищет?

pos функция выдает номер первого вхождения подстроки в строку. Полное pos(подстр,стр): integer.
Столкнулся с тем, что есть "сержант", а есть он же "младший" и он же "старший". А будет искать первое вхождение. A так же с тем что под число надо тоже одинаковое количество символов. (Чтобы потом вырезать от первого вхождения на три символа назад). А IntToStr "1 ","2 " числом не считает. Только "1", "2". Пока смотрю так. Дописывать к индексу ".00" а к значению пробелы до одинаковой длины. Т.Е. строка будет вида "1.0РЯДОВОЙ 1.0МАТРОС 2.0ЕФРЕЙТОР 999ГЕНЕРАЛИССИМУС" И искать подстроку типа "МАТРОС ".
Вообще чего я тему начал. В программе уже похожим на первый пост способом нумерую теги из xml. Тут надо сортировать по званиям, а в дальнейшем - уже и по образованию. Ну, раз говнокод - случайность. Два - тенденция. А три - диагноз. Хотелось бы найти кошерный способ. А вообще, сварганить одну процедуру подо все.

Прямой доступ к элементам сетки есть, значит можно применить алгоритм сортировки Хоара("быстрая" сортировка).
Сами алгоритмы сортировки не зависят от типа данных, которые они сортируют. Обычно в стиле STL пишут функцию
сравнения двух элементов сортируемого множества. Эта функция может использовать то отображения сортируемого множества, на множество натуральных чисел, которое вы предложили вначале.
Если не нравится конструкции if ... then, то можно использовать хеш, как структуру с постоянным времени доступа, в котором элемент сортируемого множества является ключом к своему отображению на пространство натуральных чисел.

Дело вот в чем. Сейчас покажу, что уже навоял.

В этой сетке данные не отображаются, а хранятся. После загрузки они прописываются в сетке и все. Нет никаких переменных связанных с записью и данными в ней. Работаю только с объектом StringGrid - строками, столбцами, ячейками. Конечно, значение в определенной ячейки могу считать. (5-я колонка). Но в памяти нет ни массива ни записи - только вспомогательные переменные. И менять местами строки надо от содержимого ячеек.
А с Хоаром невкуриваю. Он же отсортирует мне по алфавиту, только быстрее?

[Crazy]

Судя по этому коду с StringGrid можно работать как с двухмерным массивом(матрицей)
Даже есть код QuickSort.

Код: Выделить всё

Сортировка столбца:

type TStringGridExSortType = (srtAlpha,srtInteger,srtDouble);

procedure GridSort(SG : TStringGrid; ByColNumber,FromRow,ToRow : integer;
                   SortType : TStringGridExSortType = srtAlpha);
var Temp : TStringList;

    function SortStr(Line : string) : string;
    var RetVar : string;
    begin
      case SortType of
           srtAlpha   : Retvar := Line;
           srtInteger : Retvar := FormatFloat('000000000',StrToIntDef(trim(Line),0));
           srtDouble  : try
                          Retvar := FormatFloat('000000000.000000',StrToFloat(trim(Line)));
                        except
                          RetVar  := '0.00';
                        end;
      end;

      Result := RetVar;
    end;

    // Рекурсивный QuickSort
    procedure QuickSort(Lo,Hi : integer; CC : TStrings);

        procedure Sort(l,r: integer);
        var  i,j : integer;
             x   : string;
        begin
          i := l; j := r;
          x := SortStr(CC[(l+r) DIV 2]);
          repeat
            while SortStr(CC[i]) < x do inc(i);
            while x < SortStr(CC[j]) do dec(j);
            if i <= j then begin
              Temp.Assign(SG.Rows[j]);      // Меняем местами 2 строки
              SG.Rows[j].Assign(SG.Rows[i]);
              SG.Rows[i].Assign(Temp);
              inc(i); dec(j);
            end;
          until i > j;
          if l < j then sort(l,j);
          if i < r then sort(i,r);
        end;

     begin {quicksort};
       Sort(Lo,Hi);
     end;

Что бы сортировала по смыслу можно явно использовать вашу функцию rang в строках

Код: Выделить всё

            while SortStr(CC[i]) < x do inc(i);
            while x < SortStr(CC[j]) do dec(j);

или же написать функцию, которая сравнивает А с Б и выдает true, если А младше по званию, иначе false.

Тут только вариации в реализации функции rang.

[begin2009]

Crazy, спасибо, буду разбираться. Но именно своя функция rang мне-то и не нравится. Именно ее я и хочу заменить на что-то по-изящнее. А сама сортировка это просто. У меня уже сортирует по проживанию, возрасту, фамилии. Но там тривиально - обычное сравнение содержимого ячеек в столбце. А здесь наверное надо было бы создать перечисляемый тип из званий (тогда и case пошел бы). Но данные из таблицы будут не этого типа, а стринг. И как их конвертировать? Фиг его знает.

[begin2009]

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

[Crazy]

Для примера можно записать все это

Код: Выделить всё

if s='РЯДОВОЙ' then i:=1;
if s='РЯДОВАЯ' then i:=1;
if s='МАТРОС' then i:=1;
if s='ЕФРЕЙТОР' then i:=2;
if s='МЛ. СЕРЖАНТ' then i:=3;
if s='СЕРЖАНТ' then i:=4;
if s='СТ. СЕРЖАНТ' then i:=5;
if s='СТАРШИНА' then i:=6;
if s='ПРАПОРЩИК' then i:=7;
if s='МИЧМАН' then i:=7;
if s='МЛ. ЛЕЙТЕНАНТ' then i:=8;
if s='ЛЕЙТЕНАНТ' then i:=9;
if s='СТ. ЛЕЙТЕНАНТ' then i:=10;
if s='КАПИТАН' then i:=11;

в таблицу, предварительно отсортировав по алфавиту строки, и хранить в файле. Дальше из файла загружать эту таблицу, а в rang выполнить алгоритм бинарного поиска по званию. Поиск займет log2(N)+1, где N число званий.

[begin2009]

Для примера можно записать все это в таблицу, предварительно отсортировав по алфавиту строки, и хранить в файле. Дальше из файла загружать эту таблицу, а в rang выполнить алгоритм бинарного поиска по званию. Поиск займет log2(N)+1, где N число званий.

Смотрел я в эту сторону. Вообще таблица тогда будет двумерная. По одному рангу - список вариантов. И поиск в строке, затем смена строки. Вот кузяво ли будет? Тоже яйцо, но вид сбоку. То что поиск в одной строке, как сейчас пытаюсь, (а строка тоже из файла) - ничуть не лучше, признаю. Может быть кто-нибудь знает как привести строку к перечисляемому типу из строк? Вот тут-то все бы проблемы решились.