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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание отчета

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

Контрольные вопросы

1) Опишите простой алгоритм сортировки.

2) Опишите алгоритм быстрой сортировки.

3) Как изменятся условия для простого алгоритма сортировки, если элементы массива нужно расположить в порядке убывания?

4) Как изменятся условия для простого алгоритма сортировки, если элементы в массиве начать располагать начиная с наибольшего?

5) Объясните назначение функции print_mas из примера в теоретической части.

6) Какое количество операций сравнения потребуется для простого алгоритма сортировки при количестве элементов, равном шести?

7) Как связаны между собой значения, обозначенные одинаковыми буквами со штрихом и без штриха?

––––––––––––––––––––––––––––––––––––––––––

1. К е р н и г а н Б. Язык программирования C / Б. К е р н и г а н, Д. Р и т -

ч и. М.: Вильямс, 2009. 304 с.

ПРИЛОЖЕНИЕ

ПРИМЕР ТЕСТИРОВАНИЯ ФУНКЦИЙ

// Пример тестирования функций

// Для вывода отладочных сообщений нужно определить символ DEBUG_MAX

// Сделать это можно при компиляции с помощью ключа –D:

// Например: «C:\MinGW\bin>gcc d:/work/prog4_1.c -D DEBUG_MAX»

#include "stdio.h"

int max_len_equ_symb(char* str, int n)

// Функция находит количество элементов в наиболее длинной последовательности элементов в массиве str

// n - количество элементов в массиве str

{

int i; // Текущий просматриваемый символ

int l=1; // Максимальное количество одинаковых символов среди просмотренных

int m=1; // Текущее количество символов

char c=str[0]; // Последний встретившийся символ

for(i=1; i<n; i=i+1)

{

if(str[i]==c)

m=m+1;

else

{

m=1;

c=str[i];

}

if(m>l)

l=m;

// Это директивы препроцессора

// Все, что между ними, будет включено в программу только в случае, если определен символ DEBUG_MAX

#ifdef DEBUG_MAX

О к о н ч а н и е п р и л.

printf("i = %i, l= %i \n", i, l); // Это отладочные сообщения, которые будут печататься только при отладке. Выводим на экран интересующие нас переменные

#endif

}

return l;

}

// В примере тесты проводятся в главной функции программы

// В общем случае нужно создавать тестирующие функции для каждой созданной функции

int main()

{

int l, n=10;

// Строки, на которых мы будем тестировать нашу функцию:

char str1[]="aaabbbccdd\0";

char str2[]="abbbbbccdd\0";

char str3[]="aabbbcdddd\0";

l = max_len_equ_symb(str1, n);

printf("\nTEST 1\n str=%s,\n l=%i\n", str1,l);

// Для первой строки функция должна выдать результат 3

if (l==3)

printf("Test passed\n\n");

else

printf("Test fail\n\n");

l = max_len_equ_symb(str2, n);

printf("\nTEST 1\n str=%s,\n l=%i\n", str2,l);

if (l==5)

printf("Test passed\n\n");

else

printf("Test fail\n\n");

l = max_len_equ_symb(str3, n);

printf("\nTEST 1\n str=%s,\n l=%i\n", str3,l);

if (l==4) printf("Test passed\n\n");

else

printf("Test fail\n\n");}

Учебное издание

АЛЬТМАН Евгений Анатольевич,

АЛЕКСАНДРОВ Александр Владимирович,

АНАНЬЕВА Надежда Геннадьевна,

АКТАЕВ Нуркен Ерболатович

ВВЕДЕНИЕ В ПРОГРАММИРОВАНИЕ

____________________________________

Редактор Н. А. Майорова

Корректор Д. А. Волнина

* * *

Подписано в печать.05.2012. Формат 60 ´ 84 ¹/₁₆.

Плоская печать. Бумага офсетная. Усл. печ. л. 1,9. Уч.-изд. л. 2,2.

Тираж 100 экз. Заказ  .

* *

Редакционно-издательский отдел ОмГУПСа

Типография ОмГУПСа

*

644046, г. Омск, пр. Маркса, 35