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

Вопросы

Набор для практики

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

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

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

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

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

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

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

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

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

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

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

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

в) разность (числа, принадлежащие первому множеству, но не второму);

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

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

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

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

Литература

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

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

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

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

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

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

7. Хусаинов Б.С. Структуры и алгоритмы обработки данных. Примеры на языке Си. Учебное пособие. - М.: Финансы и статистика, 2004. – 464 с.

Дата добавления: 2014-01-04