Работа с файлами (C++). Лекция 6 по основам программирования

1. Лекция 6

ЛЕКЦИЯ 6
ОСНОВЫ ПРОГРАММИРОВАНИЯ

2. Работа с файлами

РАБОТА С ФАЙЛАМИ
#include <fstream>
• для чтения данных из файла используются
объекты типа ifstream (input file stream)
• для записи данных в файл используются объекты
типа ofstream (output file stream).
ifstream in; // Поток in для чтения
ofstream out; // Поток out для записи

3. Работа с файлами

РАБОТА С ФАЙЛАМИ
• Чтобы привязать тот или иной поток к файлу
(открыть файл для чтения или для записи)
используется метод open, которому необходимо
передать
параметр
–
текстовую
строку,
содержащую имя открываемого файла.
in.open("input.txt");
out.open("output.txt");

4. Работа с файлами

РАБОТА С ФАЙЛАМИ
• После открытия файлов и привязки их к
файловым потокам, работать с файлами
можно так же, как со стандартными потоками
ввода-вывода cin и cout.
out<<x;
in>>x;

5. Работа с файлами

РАБОТА С ФАЙЛАМИ
• Для
закрытия
ранее
открытого
файла
используется метод close() без аргументов:
in.close();
out.close();
• Закрытый файловый поток можно переоткрыть
заново при помощи метода open, привязав его к
тому же или другому файлу.

6. Работа с файлами

РАБОТА С ФАЙЛАМИ
• Также можно использовать в качестве условия
результат,
возвращаемой
операцией
считывания. Если считывание было удачным, то
результат
считается
истиной,
а
если
неудачным – ложью.
• Считывание последовательности целых чисел:
int d;
while(in>>d)
{
}

7. Линейный поиск

ЛИНЕЙНЫЙ ПОИСК
• Если данные не упорядочены, то найти искомый
элемент можно только путем последовательного
перебора всех элементов.
for (i=0; i<n; i++)
if (A[i]==B) break;
if (i != n) ...найден...
• Поиск
значения
путем
последовательного
перебора всех элементов называется линейным
поиском.
• Сложность алгоритма - O(N).

8. Двоичный (бинарный) поиск

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК
• Если данные упорядочены, то найти искомый
элемент можно значительно быстрее.
• Алгоритм двоичного
или бинарного поиска
основан
на
делении пополам
текущего
интервала поиска. В основе его лежит тот факт,
что при однократном сравнении искомого
элемента и некоторого элемента массива мы
можем определить, справа или слева от
текущего следует искать.

9. Двоичный (бинарный) поиск

ДВОИЧНЫЙ (БИНАРНЫЙ) ПОИСК
• искомый интервал поиска делится пополам и по
значению элемента массива в точке деления
определяется, в какой части следует искать
значение на следующем шаге цикла;
• для выбранного интервала поиск повторяется;
• при
«сжатии»
интервала
в
0
поиск
прекращается;
• в качестве начального интервала выбирается
весь массив.
• Сложность алгоритма - O(log(N)).

10. Поиск в неупорядоченном массиве

ПОИСК В НЕУПОРЯДОЧЕННОМ
МАССИВЕ
• Задача: дан одномерный неупорядоченный
массив, состоящий из целых чисел. Проверить,
содержится ли данное число в этом массиве.
• Простой метод (последнее вхождение):
• int j = -1;
• for (i=0; i < n; i++)
• if (a[i] == k) j = i;
• «Барьерный» метод (первое вхождение):
• a[n+1] = k;
• for (i=0; a[i] != k; i++);

11. Бинарный поиск в упорядоченных массивах

БИНАРНЫЙ ПОИСК В
УПОРЯДОЧЕННЫХ МАССИВАХ
l=0;
r=N-1;
while (l<r) {
m=(l+r)/2;
if (a[m]<k) l=m+1;
else r=m;
}
if (a[r]==k) cout<<r;
else cout<<"-1";

12. Бинарный поиск для монотонных функций

БИНАРНЫЙ ПОИСК ДЛЯ
МОНОТОННЫХ ФУНКЦИЙ
• Задача: для данного вещественного числа x (x≥1)
найти кубический корень с заданной точностью.
r = x;
l = 1;
while (fabs(l-r)>eps) {
m=(l+r)/2;
if (m*m*m<x) l=m;
else r=m;
}

13. Бинарный поиск по ответу

БИНАРНЫЙ ПОИСК ПО ОТВЕТУ
• Пусть у нас есть функция f, которая принимает
значения "истина" (1) или "ложь" (0), заданная на
множестве [0..maxval].
• При этом она обладает тем свойством, что
сначала все значения истинны, а потом все
ложны. [1, 1, ... , 1, 0, 0, ... , 0] - значения функции.
• Иначе говоря, это означает, что
• (f(x) и y <= x) => f(y).
• Искомый элемент - самая правая единица в
массиве
(к
отсортированному
массиву
применяется обычный бинарный поиск).

14. Бинарный поиск по ответу

БИНАРНЫЙ ПОИСК ПО ОТВЕТУ
• Обычный бинарный поиск - частный случай
бинарного поиска по ответу.
• Пусть нам дан массив, отсортированный по
возрастанию. Требуется найти самое правое
вхождение элемента key в массив.
• Тогда положим f(x) = (x <= key).
• Задача сведена к бинарному поиску по ответу.

15. ЗАДАЧА СОРТИРОВКИ

• Пусть есть последовательность a0, a1... an и
функция сравнения, которая на любых двух
элементах последовательности принимает одно
из трех значений: меньше, больше или равно.
• Задача сортировки состоит в перестановке
членов последовательности таким образом,
чтобы выполнялось условие: ai <= ai+1, для всех i от
0 до n.

16. Алгоритм сортировки

АЛГОРИТМ СОРТИРОВКИ
• Алгоритм сортировки — это алгоритм для
упорядочения элементов в последовательности.
• Та
часть
элемента
данных,
которая
идентифицирует его и используется для поиска,
называется ключом.
• Остальная часть несет в себе содержательную
информацию,
которая
извлекается
и
используется из найденного элемента данных.

17. оценка алгоритмов сортировки

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ
• Время сортировки — основной параметр,
характеризующий быстродействие алгоритма.
Называется также вычислительной сложностью.
Для сортировки важны худшее, среднее и
лучшее поведения алгоритма в терминах
размера последовательности n.
• Для типичного алгоритма хорошее поведение —
это O(n log n) и плохое поведение — это O(n2).
• Идеальное поведение для сортировки — O(n).

18. оценка алгоритмов сортировки

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ
• Память — ряд алгоритмов требует выделения
дополнительной
памяти
под
временное
хранение данных. Как правило, эти алгоритмы
требуют O(log n) памяти. При оценке не
учитывается место, которое занимает исходный
массив
и
независящие
от
входной
последовательности затраты, например, на
хранение кода программы (так как всё это
потребляет O(1)). Алгоритмы сортировки, не
потребляющие дополнительной памяти, относят к
сортировкам на месте.

19. оценка алгоритмов сортировки

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ
• Устойчивость — устойчивая сортировка не
меняет взаимного расположения элементов с
одинаковыми ключами.
• Естественность поведения — эффективность
метода при обработке уже упорядоченных или
частично упорядоченных данных. Алгоритм ведёт
себя
естественно,
если
учитывает
эту
характеристику входной последовательности и
работает лучше.

20. оценка алгоритмов сортировки

ОЦЕНКА АЛГОРИТМОВ СОРТИРОВКИ
• Использование операции сравнения. Алгоритмы,
использующие
для
сортировки
сравнение
элементов
между
собой,
называются
основанными на сравнениях.
• Минимальная трудоемкость худшего случая для
этих алгоритмов составляет O(n log n), но они
отличаются гибкостью применения.
• Для специальных случаев (типов данных)
существуют более эффективные алгоритмы.

21. Классификация алгоритмов сортировки

КЛАССИФИКАЦИЯ АЛГОРИТМОВ
СОРТИРОВКИ
• Признаками классификации могут быть:
• структуры
данных,
используемые
сортировке (массивы, списки, деревья),
• местонахождение
данных
–
(внутренняя) и в файлах (внешняя).
в
при
памяти
• эффективность (трудоемкость) алгоритмов.

22. Классификация алгоритмов сортировки

КЛАССИФИКАЦИЯ АЛГОРИТМОВ
СОРТИРОВКИ

23. Квадратичные и субквадратичные алгоритмы сортировки

КВАДРАТИЧНЫЕ И СУБКВАДРАТИЧНЫЕ
АЛГОРИТМЫ СОРТИРОВКИ
НЕ ИСПОЛЬЗУЮЩИЕ ДОПОЛНИТЕЛЬНУЮ ПАМЯТЬ

24. Сортировка пузырьком

СОРТИРОВКА ПУЗЫРЬКОМ
• При
проходе
снизу
вверх
по
массиву
сравниваются пары соседних элементов. Если
элементы
некоторой
пары
находятся
в
неправильном порядке, то меняем их местами.

25. Сортировка пузырьком

СОРТИРОВКА ПУЗЫРЬКОМ
• Производился ли на i-проходе обмен? Если нет алгоритм заканчивает работу.
• Шейкер-сортировка: направление следующих
один за другим проходов меняется.

26. Сравнительный анализ

СРАВНИТЕЛЬНЫЙ АНАЛИЗ
• Среднее
количество
сравнений,
хоть
и
уменьшилось, но остается O(n2), в то время как
число обменов не изменилось. Среднее(оно же
худшее)
количество
операций
остается
квадратичным.
• Дополнительная память не требуется.
• Поведение
усовершенствованного
(но
не
начального) метода довольно естественное,
почти
отсортированный
массив
будет
отсортирован намного быстрее случайного.
• Сортировка
пузырьком
устойчива,
однако
шейкер-сортировка утрачивает это качество.

27. Сортировка выбором

СОРТИРОВКА ВЫБОРОМ
• Идея метода состоит в том, чтобы создавать
отсортированную последовательность путем
присоединения к ней одного элемента за
другим в правильном порядке.
• Будем строить готовую последовательность,
начиная с левого конца массива. Алгоритм
состоит из n последовательных шагов, начиная от
нулевого и заканчивая (n-1)-м.

28. Сортировка выбором

СОРТИРОВКА ВЫБОРОМ
• На i-м шаге выбираем min(a[i] ... a[n]) и меняем
его местами с a[i].
• Вне зависимости от номера текущего шага i,
последовательность
a[0]...a[i]
является
упорядоченной.

29. Сортировка выбором

СОРТИРОВКА ВЫБОРОМ
• n + (n-1) + (n-2) + (n-3) + ... + 1 = 1/2 * ( n2+n ) = T (n2)
• Результат ее сортировки можно увидеть уже
после шага 0, так как больше обменов не будет.
Порядок ключей 2a, 2b был изменен на 2b, 2a, так
что метод неустойчив.
• Если
входная
последовательность
почти
упорядочена, то сравнений будет столько же,
значит алгоритм ведет себя неестественно.

30. Сортировка вставками

СОРТИРОВКА ВСТАВКАМИ
• В сортировке пузырьком на i-м шаге элементы
a[0]...a[i] стоят на правильных местах и никуда
более не переместятся.
• При сортировке вставками последовательность
a[0]...a[i]
упорядочена.
(более
слабое
утверждение)
• При этом по ходу алгоритма в нее будут
вставляться все новые элементы.

31. Сортировка вставками

СОРТИРОВКА ВСТАВКАМИ
• На следующем, (i+1)-м каждом шаге алгоритма
берем a[i+1] и вставляем на нужное место в
готовую часть массива.
• Поиск подходящего места для очередного
элемента
входной
последовательности
осуществляется
путем
последовательных
сравнений с элементом, стоящим перед ним.
• В зависимости от результата сравнения элемент
либо остается на текущем месте(вставка
завершена), либо они меняются местами и
процесс повторяется.

32. Сортировка вставками

СОРТИРОВКА ВСТАВКАМИ
• Таким образом, в процессе вставки мы
"просеиваем" элемент x к началу массива,
останавливаясь в случае, когда:
1. Найден элемент, меньший x или
2. Достигнуто начало последовательности.

33. Сортировка вставками

СОРТИРОВКА ВСТАВКАМИ
• Аналогично сортировке выбором, среднее, а
также худшее число сравнений и пересылок
оцениваются как T(n2).
• Дополнительная память не используется.
• Хорошим показателем сортировки является
весьма
естественное
поведение:
почти
отсортированный массив будет досортирован
очень быстро.
• Алгоритм устойчив.

34. Сортировка вставками

СОРТИРОВКА ВСТАВКАМИ
• Заметим, что на каждом шаге внутреннего
цикла проверяются 2 условия.
• Можно объединить из в одно, поставив в начало
массива специальный сторожевой элемент. Он
должен быть заведомо меньше всех остальных
элементов массива.
• Тогда при j=0 будет заведомо верно a[0] <= x.
Цикл остановится на нулевом элементе, что и
было целью условия j>=0.
• Для окончания сортировки возвращаем элемент.

35. Сравнение алгоритмов

СРАВНЕНИЕ АЛГОРИТМОВ
Название
Лучшее
время
Среднее
Худшее
Память
Устойчивость
Сортировка
пузырьком
(Bubble Sort)
Да
Сортировка
вставками
(Insertion Sort)
Да
Сортировка
выбором
(Selection Sort)
Нет
Обмены (в
среднем)

36. Сортировка Шелла

СОРТИРОВКА ШЕЛЛА
• Алгоритм сортировки массива a[0].. a[15].
1. Вначале сортируем простыми вставками
каждые 8 групп из 2-х элементов (a[0], a[8[),
(a[1], a[9]), ... , (a[7], a[15]).
2. Далее сортируем каждую из четырех групп по 4
элемента (a[0], a[4], a[8], a[12]), ..., (a[3], a[7],
a[11], a[15]).
3. Далее сортируем 2 группы по 8 элементов,
начиная с (a[0], a[2], a[4], a[6], a[8], a[10], a[12],
a[14]).
4. В конце сортируем вставками все 16
элементов.

37. Сортировка Шелла

СОРТИРОВКА ШЕЛЛА

38. Сортировка Шелла

СОРТИРОВКА ШЕЛЛА
• Приращение
расстояние
между
сортируемыми элементами, в зависимости от
прохода.
• Формула Седжвика:
• последовательность вычисляется в порядке,
противоположном используемому.
• начальное приращение выбирается по правилу:
начинаем с inc[s-1], если 3*inc[s] > size.
• среднее количество операций: O(n7/6), в худшем
случае - порядка O(n4/3).

39. Сравнение алгоритмов

СРАВНЕНИЕ АЛГОРИТМОВ
• коричневая:
пузырьком;
• синяя:
шейкерная;
• розовая:
выбором;
• желтая:
вставками;
• голубая:
вставками +СО;
• фиолетовая:
Шелла.

40. Контрольная работа N2

КОНТРОЛЬНАЯ РАБОТА N2
• Алгоритмы сортировки реализовать в виде
функций, возвращающих в качестве результата
характеристику
трудоемкости
алгоритма
(количество сравнений).
• Использовать файлы (fstream) для хранения
промежуточных и окончательных результатов
работы программы.
• Получить трудоемкость для различных значений
N=1000, 5000, 10000. Сравнить с теоретической
оценкой. Нарисовать график.