Списки + упорядочевание :), теория + ма-а-аленький пример Опции

[Gl00M]

Вот у меня есть список:

Код

Иванова Ирина Ж 12-52-17
Емельянов Иван М 13-15-26
....

Ну и так далее.. в списке много повторяющихся фамилий (именно фамилий!). Как упорядочить их по невозрастанию? Т.е. на 1м месте должны, по идеи, стоять все Ивановы (т.к. их больше всего), а на последнем, допустим, Ленин. Массив сам состоит из 20 строк и 4 колонок...
спасибо!

[volvo]

То, что ты привел - не называется "по невозрастанию"... Оно называется "по убыванию частоты появления". Как у тебя массив описан?

Var
  Arr = Array[1 .. 20, 1 .. 4] Of String;

Так?

[Gl00M]

Я описываю массив так:

 const n=20; m=4;
 spis:array[1..n,1..m] of string[15]=(
 ('Ivanova',     'Irina',      'Zh', '12-54-72'),
 ('Makarov',     'Sergei',     'M',  '15-85-63'),
 ('Abakumov',    'Vladimir',   'M',  '12-21-13'),
 ('Ratchenko',   'Ivan',       'M',  '17-29-06'),
 ('Ivanova',     'Elena',      'Zh', '15-54-93'),
 ('Vetrova',     'Natalia',    'Zh', '12-23-52'),
 ('Lenin',       'Vladimir',   'M',  '14-16-09'),
 ('Makarov',     'Vitalij',    'M',  '12-35-55'),
 ('Ivanov',      'Ivan',       'M',  '15-63-85'),
 ('Evstegneeva', 'Tatiana',    'Zh', '10-45-15'),
 ('Larina',      'Aleksandra', 'Zh', '12-35-54'),
 ('Ivanova',     'Inna',       'Zh', '12-53-65'),
 ('Vetrov',      'Sergei',     'M',  '19-12-12'),
 ('Makarova',    'Anna',       'Zh', '15-31-97'),
 ('Evstegneeva', 'Svetlana',   'Zh', '12-15-74'),
 ('Petrov',      'Petr',        'M',  '14-65-66'),
 ('Petrova',     'Nadezhda',   'Zh', '14-65-66'),
 ('Abakumova',   'Ludmila',    'Zh', '12-25-88'),
 ('Larin',       'Andrei',      'M',  '12-12-13'),
 ('Ratchenko',   'Elena',      'Zh', '17-29-06')
                                       );

volvo, я спросил "Как упорядочить по невозрастанию?.е. на 1м месте должны, по идеи, стоять все Ивановы (т.к. их больше всего), а на последнем, допустим, Ленин.", т.к. в задании так сказано... ))

Сообщение отредактировано: volvo - 3.11.2006 22:41

[klem4]

Поиск рулит
Если надо вывести список людей по алфавитному порядку

[volvo]

Значит, тогда так:
сначала сортируешь массив любым способом (из FAQ-а) по невозрастанию ПЕРВОГО элемента (фамилии), а потом (с уже отсортированным массивом) делаешь следующее:

1) ищешь максимальную последовательность одинаковых подряд идущих фамилий (запоминая ее начало, т.е. ты должен в любой момент знать, где в массиве начинается самая длинная последовательность одинаковых фамилий, и сколько именно одинаковых фамилий она содержит)...
2) когда макс. последовательность найдена, просто меняешь местами max (это ее длина) первых элементов массива с элементами, начинающимися с max_pos (это - индекс начала максимальной последовательности)...
3) затем начинаешь искать следующую макс. последовательность. Естественно, что первые max элементов в расчет уже приниматься не должны, они уже стоят на мечтах, поэтому начинаешь с max+1...

Продолжать до тех пор, пока общее число перемещенных на втором этапе элементов не сравняется с длиной исходного массива...

Код не привожу, ибо "Теория"

klem4, не то...

Надо вывести не просто по алфавиту, а по частоте фамилии...

[Gl00M]

Спасибо, volvo и klem4, за подсказку!
Код и не нужен был... я ж осознанно в теорию писал! Будут еще вопросы - напишу!

[мисс_граффити]

2) когда макс. последовательность найдена, просто меняешь местами max (это ее длина) первых элементов массива с элементами, начинающимися с max_pos (это - индекс начала максимальной последовательности)...

если менять местами, нарушится отсортированность.
то есть у нас есть:

Иванов Иван
Иванов Петр
Сидоров Иван
Сидоров Денис
Петров Дмитрий
Петров Александр
Петров Павел.

Если поменять, получим:

Петров Дмитрий
Петров Александр
Петров Павел
Сидоров Денис
Иванов Иван
Иванов Петр
Сидоров Иван

тут что-то типа сортировки со вставкой: старое надо сдвигать, а на его место ставить новое.

[volvo]

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

[мисс_граффити]

возможно, я неправильно поняла...
просто как раз на лекции раз 8 повторили, чем обменные сортировки отличаются от сортировок со вставкой, вот и зациклилась