Практическая работа " Сортировка элементов списка"

уровень А

1. Написать программу, которая сортирует список из N элементов по возрастанию методом «пузырька» и считает при этом количество произведённых перестановок. Протестировать программу на следующих исходных данных:

а) 2 5 1 6 4 10 4 2

б) 1 2 5 6 -4 0 11 12

в) 12 10 6 4 2 1 0

2. Написать программу, которая сортирует список из N элементов по убыванию методом «пузырька» и считает при этом количество произведённых перестановок. Протестировать программу на следующих исходных данных:

а) 2 5 1 6 4 10 4 2

б) 1 2 5 6 -4 0 11 12

в) 12 10 6 4 2 1 0

уровень В

1. Усовершенствовать метод «пузырька» таким образом, чтобы не выполнялись лишние перестановки, то есть, если при последнем прохождении не было совершено ни одной перестановки, то список считается уже отсортированным и происходит выход из цикла. Протестировать программу на исходных данных из 1 задачи 1 уровня А.

2. Написать программу, которая сортирует по возрастанию элементы только с чётными номерами списка из N элементов методом «пузырька».

Пример

Список: 2 5 1 6 4 10 4 2

Результат: 2 2 1 5 4 6 4 10

Протестировать программу на приведённом выше примере и двух других произвольных тестах.

уровень С

1. Сортировка выбором. Дан список A[N]. Требуется переставить элементы так, чтобы они были расположены по убыванию. Для этого в списке, начиная с первого, выбирается наибольший элемент и ставится на первое место, а первый – на место наибольшего. Затем, начиная со второго, эта процедура повторяется. Написать программу сортировки выбором и протестировать её на трёх различных тестах.

2. Сортировка вставками. Дан список A[N]. Переставить элементы в порядке возрастания по следующему правилу. Пусть a_1£a_2£a_3£…£a_i. Берётся следующее число a_i+1 и вставляется в последовательность так, чтобы новая последовательность была также возрастающей. Процесс производится до тех пор, пока все элементы от i+1 до n не будут перебраны. Протестировать программу на трёх различных тестах.