3. Сложный алгоритм сортировки

Рассмотренный выше алгоритм сортировки требует значительного числа операций сравнения. Существуют алгоритмы, которые решают эту задачу быстрее.

Алгоритм сортировки слиянием (или быстрая сортировка) в рекурсивной форме описывается следующим образом:

Сортировать первую половину массива

Сортировать вторую половину массива

Объединить результат сортировок

Функция объединения результатов сортировок (слияние) работает достаточно быстро, она из двух массивов, отсортированных определенным образом, переписывает элементы в другой массив. Учитывая, что элементы в массивах отсортированы, для того чтобы определить следующий элемент, который нужно переписать, достаточно сравнить первые из еще не переписанных элементов массива.

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

Тело цикла содержит работу по определению индексов элементов объединяемых массивов и саму процедуру слияния.

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

2. Задание к работе

Дан массив строк. Вывести на экран все слова, являющиеся анаграммами.

Анаграммами называются слова, состоящие из одинаковых букв, отличающихся лишь порядком их следования. Например: автор – товар – отвар – тавро – …; апельсин – спаниель.

Для поиска анаграмм нужно произвести следующие действия:

отсортировать буквы всех слов по алфавиту;

реализовать функцию сравнения строк;

отсортировать слова с сортированными буквами по алфавиту. Для этого нужно создать массив индексов и при сортировке переставлять элементы в массиве индексов, не изменяя массив слов;

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

Закодируем варианты сортировки следующим образом: по убыванию (код 0х) – по возрастанию (код 1х); с начала (во внутреннем цикле данные просматриваются с начала, используются операции типа i++, код х0) – с конца (во внутреннем цикле данные просматриваются с конца, используются операции типа i--, код х1).

Номер варианта задания равен остатку от деления номера студента по журналу на 16. Этот остаток кодируется четырьмя битами. Старшие два бита означают тип сортировки букв в слове, два младших означают тип сортировки индексов. Например, вариант 0110 (6) означает, что буквы нужно сортировать по убыванию, начиная с конца, а массив индексов нужно сортировать по возрастанию, начиная с начала.

В простейшем варианте можно реализовать сортировку пузырьком (поэлементную). Студенты, претендующие на повышенную оценку автоматом, должны реализовать быструю сортировку.