Материалы для практики - Обработки данных

^ Материалы для практики
Вопросы

  1. Чем можно разъяснить обилие алгоритмов сортировок?

  2. Почему сейчас не существует универсального метода сортировки?

  3. Как соблюдение параметров стойкости и естественности оказывает влияние на трудозатратность метода сортировки?

  4. За счет чего в методах стремительных Материалы для практики - Обработки данных сортировок происходит выигрыш при выполнении операций сопоставления и перестановок?

  5. Какие из перечисленных алгоритмов более эффективны на практически отсортированных массивах: бинарная пирамидальная сортировка, сортировка слиянием, сортировка Шелла и сортировка Хоара? За счет Материалы для практики - Обработки данных чего происходит выигрыш?

  6. Почему методы стремительных сортировок не дают огромного выигрыша при малых размерах массивов?

  7. В чем достоинства и недочеты по отношению друг к другу последующих алгоритмов сортировок: бинарная пирамидальная сортировка, сортировка Материалы для практики - Обработки данных слиянием, сортировка Шелла и сортировка Хоара?

  8. Как найти, какому методу сортировки дать предпочтение при решении задачки?


Упражнения

  1. На основании приведенных в лекции функций реализуйте методы внутренних сортировок.

  2. Даны два целочисленных файла, упорядоченных по возрастанию. Сформировать Материалы для практики - Обработки данных 3-ий файл на базе данных, который также упорядочен и представляет операцию с элементами начальных файлов:

    1. объединение (содержит числа, принадлежащие хотя бы одному из множеств);

    2. перечисление (числа, принадлежащие обоим огромным количествам);

    3. разность Материалы для практики - Обработки данных (числа, принадлежащие первому огромному количеству, но не второму);

    4. симметричную разность (объединение разностей множеств).

  3. Заданы N (N≤5000) попарно разных длин отрезков. Вычислить количество методов, которыми из отрезков можно сложить треугольник.

  4. Дана целочисленная квадратная матрица Материалы для практики - Обработки данных размером n. Упорядочить значения так, чтоб

.

  1. Дан целочисленный массив. Сделайте проверку уникальности. Удалите из массива повторные вхождения чисел.



Литература

  1. Ахо А., Хопкрофт Дж., Ульман Д. Структуры данных и методы. Уч. пособие / А Материалы для практики - Обработки данных. Ахо, Дж. Хопкрофт, Д. Ульман. – М.: Вильямс, 2000. – 384 с.

  2. Кнут Д.Э. Искусство программирования. Том 3. Сортировка и поиск, 3-е изд.: Пер. с англ.: Уч. пос. / Д.Э. Кнут. – М.: Вильямс, 2000. – 832 с Материалы для практики - Обработки данных.

  3. Кормен Т., Леверсон Ч., Ривест Р. Методы. Построение и анализ / Т. Кормен, Ч. Леверсон, Р. Ривест. – М.: МЦНМО, 1999. – 960 с.

  4. Подбельский, В.В. Программирование на языке Си: учеб. пособие / В.В. Подбельский Материалы для практики - Обработки данных, С.С. Фомин. – М.: Деньги и статистика, 2004. – 600 с.

  5. Подбельский, В.В. Язык Си++: учеб. пособие / В.В. Подбельский. – М.: Деньги и статистика, 2005. – 560 с.




  1. Сэджвик Р. Фундаментальные методы на С++. Части 1-4. Анализ, структуры данных, сортировка Материалы для практики - Обработки данных, поиск / Р. Сэджвик. – М.: Диасофт, 2001. – 687 с.

  2. Хусаинов Б.С. Структуры и методы обработки данных. Примеры на языке Си. Учебное пособие / Б.С. Хусаинов. – М.: Деньги и статистика, 2004. – 464 с.
^ 11. Методы сортировки массивов. Наружняя Материалы для практики - Обработки данных сортировка
Короткая инструкция

В этой теме рассматриваются определение и систематизация алгоритмов наружных сортировок, понятия фаз и путей в методах наружных сортировок, приводятся описания и реализации алгоритмов наружной сортировки слиянием и естественной сортировки Материалы для практики - Обработки данных.


^ Цель исследования темы

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

^ 11.1. Главные понятия алгоритмов наружных сортировок
Наружные сортировки используются к данным, которые хранятся Материалы для практики - Обработки данных во наружной памяти. При выполнении таких сортировок требуется работать с данными, расположенными на наружных устройствах поочередного доступа. Для файлов, расположенных на таких устройствах в каждый момент времени доступен только один Материалы для практики - Обработки данных компонент последовательности данных, что является значимым ограничением по сопоставлению с сортировкой массивов, где всегда доступен каждый элемент.

Наружняя сортировка – это сортировка данных, которые размещены на наружных устройствах и не вмещающихся в оперативку.

Данные, хранящиеся Материалы для практики - Обработки данных на наружных устройствах, имеют большой объем, что не позволяет их полностью переместить в оперативку, отсортировать с внедрением 1-го из алгоритмов внутренней сортировки, а потом возвратить их на наружное устройство. В данном Материалы для практики - Обработки данных случае производилось бы малое количество проходов через файл, другими словами было бы однократное чтение и однократная запись данных. Но на практике приходится производить чтение, обработку и запись данных в файл по блокам, размер которых Материалы для практики - Обработки данных находится в зависимости от операционной системы и имеющегося объема оперативки, что приводит к повышению числа проходов через файл и приметному понижению скорости сортировки.

К более известным методам наружных сортировок относятся:

Из представленных наружных сортировок более принципиальным является способ сортировки при помощи слияния. До того как обрисовывать метод сортировки Материалы для практики - Обработки данных слиянием введем несколько определений.

Главным понятием при использовании наружной сортировки является понятие серии. Серия (упорядоченный отрезок) – это последовательность частей, которая упорядочена по ключу.

Количество частей в серии именуется длиной серии. Серия, состоящая Материалы для практики - Обработки данных из 1-го элемента, упорядочена всегда. Последняя серия может иметь длину наименьшую, чем другие серии файлов. Наибольшее количество серий в файле N (все элементы не упорядочены). Малое количество серий одна (все элементы упорядочены Материалы для практики - Обработки данных).

В базе большинства способов наружных сортировок лежит процедура слияния и процедура рассредотачивания. Слияние – это процесс объединения 2-ух (либо более) упорядоченных серий в одну упорядоченную последовательность с помощью повторяющегося выбора частей доступных Материалы для практики - Обработки данных на этот момент. Рассредотачивание – это процесс разделения упорядоченных серий на два и несколько вспомогательных файла.

Фаза – это деяния по однократной обработке всей последовательности частей. Двухфазная сортировка – это сортировка, в какой раздельно реализуется две фазы: рассредотачивание Материалы для практики - Обработки данных и слияние. Однофазовая сортировка – это сортировка, в какой объединены фазы рассредотачивания и слияния в одну.

Двухпутевым слиянием именуется сортировка, в какой данные распределяются на два вспомогательных файла. Многопутевым слиянием именуется сортировка, в Материалы для практики - Обработки данных какой данные распределяются на N (N > 2) вспомогательных файлов.

Общий метод сортировки слиянием

Поначалу серии распределяются на два либо более вспомогательных файлов. Данное рассредотачивание идет попеременно: 1-ая серия записывается в 1-ый Материалы для практики - Обработки данных вспомогательный файл, 2-ая – во 2-ой и т.д. до последнего вспомогательного файла. Потом снова запись серии начинается в 1-ый вспомогательный файл. После рассредотачивания всех серий, они соединяются воединыжды в более длинноватые упорядоченные отрезки, другими Материалы для практики - Обработки данных словами из каждого вспомогательного файла берется по одной серии, которые соединяются. Если в каком-то файле серия завершается, то переход к последующей серии не осуществляется. Зависимо от вида сортировки сформированная более Материалы для практики - Обработки данных длинноватая упорядоченная серия записывается или в начальный файл, или в один из вспомогательных файлов. После того как все серии из всех вспомогательных файлов объединены в новые серии, позже снова начинается их рассредотачивание Материалы для практики - Обработки данных. И так до того времени, пока все данные не будут отсортированы.

Выделим главные свойства сортировки слиянием:

Разглядим главные и более Материалы для практики - Обработки данных принципиальные методы наружных сортировок более тщательно.



materialnaya-otvetstvennost-i-vziskaniya.html
materialnaya-otvetstvennost-rabotnikov-dou.html
materialnaya-otvetstvennost-storon.html