Сортировка последовательностей

Лабораторная работа № 12

«Базовые алгоритмы обработки последовательностей»

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

Теоретические сведения

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

Сортировка последовательностей

Трехленточная сортировка

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

Число пересылок: M = n*log n

Пример:

Исходная последовательность: 44 55 12 42 94 13 05 67

1. 44 55 12 42

94 18 06 67

44 94 18 55 06 12 42 67

2. 44 94 18 55

06 12 42 67

06 12 44 94 18 42 55 67

3. 06 12 44 94

18 42 55 67

06 12 18 42 44 55 67 94

Сортировка естественным слиянием

Этот метод используется, когда последовательности частично упорядочены, эти упорядоченные последовательности называют сроками или сериями, поэтому при этой сортировке объединяются серии, а не последовательности фиксированной длинны. Каждый проход состоит из фазы распределения и фазы слияния. При разделении исходной последовательности на две подпоследовательности оптимальным вариантом будет тот, когда число серий в этих последовательностях одинаково; существенно неравномерное распределение серий в подпоследовательностях маловероятно, но может случиться, что в одной из подпоследовательностей серий на одну больше, тогда лишняя серия при проходе просто копируется.

Пример:

Имеем исходную последовательность (серии разделены) -

17 31; 05 59; 13 41 43 67; 11 23 29 47; 03 07 71; 02 19 57; 37 61

объединяем серии по две, одна последняя серия лишняя -

05 17 31 59; 11 13 23 29 41 46 47 67; 02 03 07 19 57 71; 37 61

05 11 13 17 23 29 31 41 43 47 59 67; 02 03 07 19 37 57 61 71

02 03 05 07 11 13 17 19 23 29 31 37 41 43 47 57 59 61 67 71

Многопутевая сортировка

Данный метод сортировки является модификацией метода естественного слияния. Временные затраты на любую сортировку последовательностей пропорциональны числу требуемых проходов, так как при каждом проходе копируются все данные. Чтобы уменьшить число этих проходов, серии распределяют на последовательности, число которых больше 2-х. Слияние Р серий, поровну распределены в М последовательностей, дает в результате Р/М серий. Второй проход уменьшить это число до Р/M¤, третий - до Р/M3 и т.д. Поэтому общие число проходов многопутевого слияния будет равно Log m K, где К - число элементов в последовательности. Итак, в этом методе, по сравнению с методом естественно слияния, добавляются М путей распределения и слияния последовательностей.

Многофазная сортировка

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

Пример:

Имеем 2 последовательности: в первой 13 серий, во второй 8 серий. При первом проходе сливаются 8 серий в третьей последовательности, в первой остается 5. При втором проходе 5 серий из второй и третьей последовательности сливаются во второй и т.д.

1 проход: 13 8 --

2 проход: 5 -- 8

3 проход: -- 5 3

4 проход: 3 2 --

5 проход: 1 -- 2

6 проход: -- 1 1

7 проход: 1 -- --

ЗАДАНИЕ: написать программу согласно своему варианту

Вариант	Задание
1.	Дана строка символов. Определить, сколько раз в строке встречаются символы ’а’, ‘б’, ‘о’, ‘щ’, используя множественный тип.
2.	Дана последовательность символов, построить и напечатать множество, элементами которого являются встречающиеся в последовательности цифры от ‘0’ до ‘9’ и знаки препинания.
3.	Дана строка символов. Определить, каких букв – гласных или согласных – больше в этой строке.
4.	Написать программу, подсчитывающую количество различных цифр в десятичной записи натурального числа n.
5.	Написать программу, печатающую в возрастающем порядке все цифры, не входящие в десятичную запись натурального числа n.
6.	Дана последовательность символов. Напечатать первые вхождения букв в текст, сохраняя их исходный взаимный порядок.
7.	Дана последовательность символов. Напечатать все буквы, входящие в текст не менее двух раз.
8.	Дана последовательность символов. Напечатать все буквы, входящие в текст по одному разу.
9.	Дана последовательность слов русского языка, между словами – запятая, за последним словом – точка. Напечатать в алфавитном порядке: все гласные буквы, которые входят в каждое слово.
10.	Дана последовательность слов русского языка, между словами – запятая, за последним словом – точка. Напечатать в алфавитном порядке: все согласные буквы, которые не входят ни в одно слово.
11.	Дана последовательность слов русского языка, между словами – запятая, за последним словом – точка. Напечатать в алфавитном порядке: все звонкие согласные буквы, которые входят хотя бы в одно слово.
12.	Дана последовательность слов русского языка, между словами – запятая, за последним словом – точка. Напечатать в алфавитном порядке: все глухие согласные буквы, которые не входят хотя бы в одно слово.
13.	Дана последовательность слов русского языка, между словами – запятая, за последним словом – точка. Напечатать в алфавитном порядке: все согласные буквы, которые входят только в одно слово.
14.	Дана последовательность слов русского языка, между словами – запятая, за последним словом – точка. Найти число таких групп слов, которые начинаются и заканчиваются одной и той же буквой.
15.	Дана последовательность слов русского языка, между словами – запятая, за последним словом – точка. Расположить слова в порядке возрастания количества в них букв.