Организация ввода (вывода) элементов массива из файла (в файл).

Тема: поиск и сортировка данных в массивах.

Методы сортировки элементов массива

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

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

Пример. Пусть исходный массив имеет вид: . Отсортируем его в порядке возрастания:

Сортировка перемешиванием (шейкерная сортировка).

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа на-лево.

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

Сначала нужно рассмотреть подмножество массива и найти в нём максимум (или минимум). Затем выбранное значение меняют местами со значением первого неотсорти­рованного элемента. Этот шаг нужно повторять до тех пор, пока в массив не будет полностью отсортирован.

Методы поиска элемента в массиве

Бинарный поиск

Данный вид поиска применяется в отсортированном массиве.

1. Определение значения элемента в середине структуры данных. Полученное значе-ние сравнивается с ключом.
2. Если ключ меньше значения середины, то поиск осуществляется в первой половине элементов, иначе — во второй.
3. Поиск сводится к тому, что вновь определяется значение серединного элемента в выбранной половине и сравнивается с ключом.
4. Процесс продолжается до тех пор, пока не будет найден элемент со значением клю-ча или не станет пустым интервал для поиска.

Ключ - искомый элемент массива. Предположим, искомый элемент равен 3,тогда

Линейный, последовательный поиск (перебор, сквозной поиск)

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

Итоговая работа «Исследование алгоритмов сортировки и поиска данных в массивах».

Необходимо разработать и реализовать программы сортировки заданного число­вого массива действительных чисел, находящегося в файле на диске приведенными выше методами. Файл можно создать, используя блокнот, разделяя числа пробелами. Для каж-дого метода найти и вывести на экран количество операций сравнения, требуемых при его реализации. Отсортированный массив вывести в дисковый файл (ис­ходный файл сохраняется!). Исходный файл состоит из 20 положительных, отрицательных и нулевых элементов. Кроме отчета необходимо выслать исходный и отсортированный файлы.

Далее требуется реализовать алгоритмы бинарного и сквозного поиска для исход­ного массива и сравнить результаты их работы.

Приложение.

Организация ввода (вывода) элементов массива из файла (в файл).

#include <fstream>

………..

using namespace std;

ifstream inp(“I:VST\\inp.txt”);

ofstream out(“I:VST\\out.txt”);

int main()

{……………………………

for(i=0;i<20;i++) inp>>b[i];

………………………….

inp.close();

for(i=0;i<20;i++) out<<c[i]<<” ”;

out.close();

return 0;

}