Упражнения

Вопросы

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

Краткие итоги

Ключевые термины

Ключ сортировки – это часть данных, определяющая порядок элементов.

Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию.

Сортировка методом «пузырька» – это алгоритм попарного сравнения элементов одномерного массива.

Сортировка методом простого включения – это алгоритм последовательного помещения элемента массива в отсортированную часть в соответствии с ключом сортировки.

Сортировка методом простого выбора – это алгоритм последовательного обмена минимального и первого элементов неотсортированной части массива.

1. Задачи сортировок массивов имеют широкое прикладное значение.

2. Существует большое количество алгоритмов сортировок массивов, различающихся трудоемкостью.

3. При оценке трудоемкости алгоритмов учитываются критерии: количество сравнений и перестановок, время в лучшем и худшем случаях, естественность поведения.

4. К алгоритмам простых сортировок относятся: сортировка методом «пузырька», сортировка методом простого выбора, сортировка методом простого включения.

5. Простые сортировки эффективны на небольших объемах данных.

1. Почему существует большое количество алгоритмов сортировок?

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

3. Чем отличается принцип сортировки по неубыванию (невозрастанию) от сортировки по возрастанию (убыванию)?

4. На каких наборах исходных данных проявляется эффективность алгоритмов простых сортировок по сравнению друг с другом?

5. В чем заключается улучшение метода шейкер-сортировки по сравнению с пузырьковой сортировкой?

1. Отсортируйте по неубыванию методом «пузырька» одномерный целочисленный массив, заданный случайными числами на промежутке [-100; 100). Выведите на экран исходный и отсортированный массивы.

2. Отсортируйте по невозрастанию методом простого выбора одномерный вещественный массив, заданный случайными числами на промежутке [0; 50). Выведите на экран исходный и отсортированный массивы.

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

4. Массив размером 2 m + 1, где m – натуральное число, заполнен случайным образом. Найдите в массиве медиану. Медианой называется элемент ряда, делящий его на две равные части: в одной находятся элементы, которые не меньше медианы, в другой – не больше медианы.

5. Массив размером m, где m – натуральное число, заполнен случайным образом. Найдите в массиве моду. Модой называется элемент ряда, который встречается наиболее часто.

Литература

1. Керниган, Б. Язык программирования Си / Б. Керниган, Д. Ритчи. – М.: Вильямс, 2007. – 304 с.

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

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

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

5. Романов, Е.Л. Практикум по программированию на языке С++: учеб. пособие / Е.Л. Романов. – СПб: БХВ-Петербург, 2004. – 432 с.

6. С/С++. Структурное программирование: практикум / Т.А. Павловская, Ю.А. Щупак. – СПб: Питер, 2004. – 239 с.

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