Сортировка слиянием (MergeSort)

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

Домашнее задание №1.

Домашние задания

Рекомендуемые темы для эссе, рефератов и докладов

1. Методы сортировки с сохранением порядка равных элементов.

2. Методы сортировки за линейное время.

3. AVL-деревья.

4. Хэш-таблица с разрешением коллизий методом списков и универсальным хэшированием.

5. Хэш-таблица с использованием квадратичного исследования и метода умножения.

Домашнее задание 1 относится к первому модулю. Стоимость в баллах в соответствии с программой курса - 8.

Домашнее задание 2 относится ко второму модулю. Стоимость – 30 баллов.

Задачи домашнего задания

1. Закрепление знаний об алгоритмах сортировки, работающих за время O(N log N).

2. Восстановление навыков программирования на C++, полученных в рамках предыдущих курсов.

Задание

Разработать программу на языке C++, выполняющую сортировку слиянием массива вещественных чисел.

Программа должна позволять ввести с экрана несколько чисел и сортировать их по возрастанию.

Достаточна разработка консольного приложения.

Разрешается ограничить количество элементов в массиве константой, фиксируемой в момент компиляции.

В качестве отчета студент предоставляет в электронном виде программу на языке C++, выполняющую сортировку массива.

Предлагаемые этапы выполнения задания

1. Изучение теоретического материала.

2. Создание пустого консольного приложения в среде Visual Studio 2005 [7].

3. Разработка программы.

4. Отладка программы.

Теоретический материал, необходимый для выполнения домашнего задания

Алгоритм сортировки слиянием [2] основан на следующих принципах:

1. Если массив состоит из двух отсортированных частей (например, равных, но это не обязательно), то мы можем выполнить сортировку массива за время O(N).

Действительно, если последовательности A[0]..A[K-1] и A[K]..A[N-1] отсортированы, то для получения минимального элемента достаточно сравнить A[ 0 ] и A[ K ]. Найденный элемент попадает в результирующий массив и исключается из рассмотрения. Чтобы найти минимальный из оставшихся элементов, снова достаточно сравнить минимальные элементы подпоследовательностей. Если одна из подпоследовательностей закончилась – оставшиеся элементы просто берем из другой.

Слияние отсортированных последовательностей иллюстрируется на рис. 1.

Рис. 1. Слияние подпоследовательностей

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

2. Массив из двух элементов всегда состоит из двух отсортированных частей.

3. Соответственно, мы можем сначала разбить наш массив на группы по 2 элемента и сортировать их указанным методом. Таких групп будет N /2. Если останется 1 лишний последний элемент – не страшно, он считается уже отсортированной группой.

Далее мы рассматриваем группы из 4 элементов (опять же, не страшно, если последняя группа будет меньше). Каждая группа состоит из двух только что отсортированных двухэлементных групп. Значит, мы можем применить алгоритм из 1-ого пункта.

Продолжая объединение групп, в итоге мы получим отсортированный массив.

4. На шаге K рассматриваются группы из 2 ^K элементов. Время сортировки одной группы O(2 ^K), число групп N /2 ^K, общая длительность шага O(N).

Число таких шагов – log₂ N, т.к. размер группы увеличивается в два раза на каждом шаге и сортировка заканчивается, когда он станет равным N.

Таким образом, общая длительность сортировки – O(N log N).

Сортировка слиянием иллюстрируется на рис. 2.

Рис. 2. Сортировка слиянием

Описание работы с массивами в языке программирования C++

Массивом [3] называется совокупность пронумерованных данных, размещаемых в памяти подряд, одно значение за другим. В массиве можно обеспечить быстрое обращение к элементу по номеру, т.к.

A_i = A + i * S, [3.1]

где A_i - адрес элемента i, A – адрес начала массива, S – размер элемента.

Массив иллюстрируется на рис. 3.

Рис. 3. Размещение массива в памяти.

В языке программирования C++ [3] массив – один из составных типов данных. Массив объявляется в виде

TYPE NAME[ SIZE ];

где TYPE – тип элемента массива (должен быть корректным типом данных), NAME – имя массива, SIZE – размер массива (должен быть константой). Например:

double Arr[ 10 ];

const int TextSize=4096;

char Text[ TextSize ];

Для того, чтобы обратиться к элементу массива, мы пишем NAME[ INDEX ], где NAME – имя массива, INDEX – номер элемента. Например: Arr[0]=Arr[1]+Arr[2];

Циклы в C++

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

В C++ существуют три вида цикла:

1. Цикл while (с предусловием).

while (<условие>)

<операция>

Пока выполнено условие – выполнять операцию.

Пример:

char a[200];

…. //заполнение строки чем-нибудь

int i = 0;

while (i < 200 && a[i]!=’A’)

i++;

Этот код бежит по строке либо до конца строки, либо пока не встретит букву ‘A’. Так мы можем узнать, где в строке первая буква ‘A’.

2. Цикл do-while (с постусловием).

do

<операция>

while (<условие>);

Повторяет операцию, пока выполнено условие. Хотя бы один раз операция точно будет выполнена (условие проверяется после выполнения операции и определяет, идти ли на следующий шаг).

Пример:

char res=0;

do

{

printf(”Если устали – введите Y\n”);

scanf(“%c”, &res);

}

while (res!= ‘Y’);

Этот код спрашивает у пользователя, не устал ли он. Если пользователь ввел Y (Yes) – программа выходит из цикла и идет дальше, иначе спрашивает еще раз.

3. Цикл for.

for (<инициализация>; <условие>; <переход>)

<операция>

Вначале выполняется операция инициализации. После этого, если выполнено условие – выполняется операция и переход.

Пример:

for (i = 0; i < 200; i = i + 2)

A[i] = 0;

Этот код заполняет нулями четные элементы массива A с номером меньше 200.

Описание ввода-вывода в языке программирования C++

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

Основной абстракцией ввода-вывода, используемой в библиотеке STL, является поток [3]. Потоком называется объект, из которого могут быть прочитаны данные (поток ввода) или в который могут быть записаны данные (поток вывода). В роли потока может выступать экран консольного приложения, файл, какой-либо датчик и т.д. – главное, чтобы для него был реализован класс с соответствующим интерфейсом.

Основными механизмами работы с потоком являются операторы потокового ввода (>>) и потокового вывода (<<). Например, чтобы в консольном приложении считать с экрана целое число, мы напишем:

int a;

std::cin >> a;

std::cin – это стандартный объект – поток ввода с экрана консольного приложения.

Аналогично, чтобы вывести на экран вещественное число и затем перейти на следующую строку, можно написать:

double b = 4.3;

std::cout << b << std::endl;

std::cout – стандартный объект, поток вывода на экран консольного приложения. std::endl – символ конца строки

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

Именно поэтому оператор потокового вывода, как правило, имеет синтаксис (я рассматриваю вариант реализации оператора как функции, а не как метода потока):

std::ostream& operator<<(std::ostream& str, SomeType somevalue)

{

…//Вывод в str somevalue

return str;

}

Благодаря этому синтаксису результатом операции std::cout << b является сам поток cout. И когда мы применяем к этому результату операцию << std::endl – символ конца строки выводится на экран, как мы и хотели.

Основные виды потоков:

1. std::cin, std::cout, std::cerr – стандартные потоки консольного ввода-вывода.

2. std::ifstream, std::ofstream – потоки файлового ввода-вывода.

3. std::istrstream, std::ostrstream – потоки ввода-вывода в строку.

Дата добавления: 2015-01-03