Inf / inf-14-z

Тематическое занятие 14.

Усовершенствованные методы сортировки.

Задания для лабораторной работы 14.

(максимальный балл – 4)

Задание для лабораторной работы 14.

Вариант 1

1)Изучить метод быстрой сортировки (Хоара). На основе алгоритма быстрой

сортировки, реализованного в «Методических указаниях», составить программу, которая проводит сортировку массива целых чисел. (Условие упорядоченности

(возрастание/убывание) – то же, что и в задании на лабораторную работу к тематическому занятию 13.)

2)На каждом этапе сортировки выводить на экран сравниваемые элементы и их

места в массиве (индексы), а также весь массив целиком в конце каждого этапа.

3)Для массива из N элементов подсчитать количество сравнений при сортировке и сравнить с теоретической оценкой сложности алгоритма. (Факультатив: провести

сравнение для нескольких различных значений N.)

Задание для лабораторной работы 14.

Вариант 2

1)Изучить метод сортировки слиянием. На основе алгоритма рекурсивной

сортировки со слиянием, реализованного в «Методических указаниях», составить программу, которая проводит сортировку массива целых чисел. (Условие упорядоченности (возрастание/убывание) – то же, что и в задании на лабораторную работу к тематическому занятию 13.)

2)На каждом этапе сортировки выводить на экран сравниваемые элементы и их

места в массиве (индексы), а также весь массив целиком в конце каждого этапа.

3)Для массива из N элементов подсчитать количество сравнений при сортировке и сравнить с теоретической оценкой сложности алгоритма. (Факультатив: провести сравнение для нескольких различных значений N.)

Задание для лабораторной работы 14.

Вариант 3

1)Изучить метод пирамидальной сортировки. На основе алгоритма пирамидальной

сортировки, реализованного в «Методических указаниях», составить программу, которая

проводит сортировку массива целых чисел. (Условие упорядоченности (возрастание/убывание) – то же, что и в задании на лабораторную работу к тематическому занятию 13.)

2)На каждом этапе сортировки выводить на экран сравниваемые элементы и их места в массиве (индексы), а также весь массив целиком в конце каждого этапа.

3)Для массива из N элементов подсчитать количество сравнений при сортировке и

сравнить с теоретической оценкой сложности алгоритма. (Факультатив: провести сравнение для нескольких различных значений N.)

Задания для самостоятельной работы 14.

(максимальный балл – 8)

Задание для самостоятельной работы 14.

1)На основе программы работы с массивом, которая описана в домашнем задании к тематическому занятию 13, составить функцию сортировки массива методом, указанным

взадании к лабораторной работе 14. (Функция должна работать с массивами как с параметрами.)

2)Для одного и того же массива из N элементов сравнить работу простого и

усовершенствованного методов сортировки, реализованных на тематических занятиях 13 и 14, по количеству сравнений и присваиваний. (Оба метода должны проводить

сортировку по одинаковому условию – либо по убыванию, либо по возрастанию.)

3)Для обоих методов сортировки подсчитать количество сравнений элементов при сортировке и сравнить его с теоретической оценкой сложности данных алгоритмов при

различном количестве элементов N (например, при N=10, 50, 100, 500).