60. Алгоритмы сортировки и поиска. Обменные сортировки. Сортировки вставками. Сортировки выбором. Сравнительный анализ методов сортировки.

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

10.5.2. Сортировка вставками Сортировка простыми вставками в чем-то похожа на обменные методы. Однако в сортировке пузырьком можно было четко заявить, что на i-м шаге элементы a[0]...a[i] стоят на правильных местах и никуда более не переместятся. Здесь же подобное утверждение будет более слабым: последовательность a[0]...a[i] упорядочена. При этом по ходу алгоритма в нее будут вставляться все новые элементы.

На i-м шаге последовательность разделена на две части: упорядоченную a[0]...a[i] и неупорядоченную a[i+1]...a[n]. На следующем, (i+1)-м каждом шаге алгоритма берем a[i+1] и вставляем на нужное место в готовую часть массива. Поиск места для очередного элемента входной последовательности осуществляется путем последовательных сравнений с элементом, стоящим перед ним. В зависимости от результата сравнения элемент либо остается на текущем месте(вставка завершена), либо они меняются местами и процесс повторяется. Таким образом, в процессе вставки мы "просеиваем" элемент x к началу массива, останавливаясь в случае, когда 1.   найден элемент, меньший x; 2. достигнуто начало последователь-ности 10.5.3. Сортировка выбором  Идея метода состоит в том, чтобы создавать отсортированную последовательность путем присоединения к ней одного элемента за другим в правильном порядке. Будем строить готовую последователь-ность, начиная с левого конца массива. На i-м шаге выбираем наименьший из элементов a[i] ... a[n] и меняем его местами с a[i]. Последовательность шагов при n=5 изображена на рисунке ниже.

61. Последовательный поиск. Бинарный поиск. Сравнительный анализ методов поиска.

10.2.1. Линейный поиск Линейный, последовательный поиск — нахождения заданного элемента в некотором массиве. Поиск значения осуществляется простым сравнением очередного значения и искомого, если значения совпадают, то поиск считается завершённым. 10.2.2. Бинарный поиск Или метод дихотомии или метод половинного деления. Как обычно, за скорость взимается плата: массив должен быть упорядочен. Сам по себе этап предварительного упорядочения, или сортировки, обходится недешево, во всяком случае - дороже однократного линейного поиска.  

62. Файлы. Основные принципы работы с файлами. Механизм чтения данных из файла. Определение конца файла. Открытие и закрытие файлов.

Файл – это последовательность байтов, хранящихся на внешнем носителе информации. Каждый файл имеет имя. Работа с файлом поддерживается операционной системой, которая имеет средства:• создания и уничтожения файлов;• поиска файлов на внешнем носителе;• чтения и записи данных из файлов и в файлы;• открытия и закрытия файлов;

• позиционирования файлов.Открытие файла FILE* fopen (const char* fname, const char* mode);Закрытие файлаint fclose(FILE* stream); Проверка на конец файла  Каждый поток содержит индикатор конца файла, который хранится в структуре файла и устанавливается в ненулевое значение функцией чтения из файла при достижении конца файла. Состояние потока определяется функцией: int feof(FILE* file); Возвращает 0, если конец файла не достигнут. При достижении конца файла содержимое последней прочитанной порции информации не определено.