Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Алгоритм сортировки слиянием [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).
Число таких шагов – log2 N, т.к. размер группы увеличивается в два раза на каждом шаге и сортировка заканчивается, когда он станет равным N.
Таким образом, общая длительность сортировки – O(N log N).
Сортировка слиянием иллюстрируется на рис. 2.
Рис. 2. Сортировка слиянием
Описание работы с массивами в языке программирования C++
Массивом [3] называется совокупность пронумерованных данных, размещаемых в памяти подряд, одно значение за другим. В массиве можно обеспечить быстрое обращение к элементу по номеру, т.к.
Ai = A + i * S, [3.1]
где Ai - адрес элемента 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-13; Прочитано: 408 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!