7 Упорядочивание (сортировка) массива

Общие задания:

1. Ввести значения целочисленного одномерного массива, состоящего из 10 элементов. Используя алгоритм сортировки выбором, упорядочить данный массив по убыванию.

2. Ввести значения целочисленного одномерного массива, состоящего из 10 элементов. Используя алгоритм сортировки обменом, упорядочить данный массив по убыванию.

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

4. Ввести значения одномерного массива типа char, состоящего из 10 букв. Используя алгоритм сортировки выбором, упорядочить данный массив так, чтобы буквы в массиве располагались по убыванию их внутренних кодов.

Индивидуальные задания:

1. Даны натуральные n, A1,…,An (n>=4). Числа А1,…,Аn – это измеренные в сотых долях секунды результаты n спортсменов в беге на 100 м. Составить команду из четырех лучших бегунов для участи в эстафете 4х100, т.е. указать одну из четверок натуральных чисел i, j, r,l такую, что 1<=i<=j<=r<=l<=n и Ai+Aj+Ar+Al имеет наименьшее значение.

2. Даны действительные С1,…,Ср, D1,…,Dq (C1<=c2<=…<=Cp) (D1<=D2<=…<=Dq). Внести единую упорядоченность в эти массивы, получив f1, f2,…,fp+q такие, что f1<=f2<=…<=fp+q. Число сравнений не должно превосходить p+q.

3. Даны целые А1,…,An. Найти наибольшее значение, содержащееся в последовательности чисел А1,…, Аn после выбрасывания из нее одного из членов со значением max(A1,…,An).

4. Даны целые А1,…,An. Найти наибольшее значение, содержащееся в последовательности чисел А1,…, Аn после выбрасывания из нее всех членов со значением max(A1,…,An).

5. Алгоритм сортировки простыми вставками можно изменить следующим образом. Место, на которое надо вставить x_i в уже упорядоченную совокупность x₁,…, x_i-1 определятся алгоритмом деления отрезка пополам. Получается новый алгоритм , который называется - алгоритм сортировки бинарными вставками(слова «бинарная вставка» следует понимать как «вставка делением пополам »).Реализовать алгоритм сортировки бинарными вставками для сортировки элементов последовательности X1,…,Xn по возрастанию.

6. Реализовать алгоритм сортировки бинарными вставками для сортировки элементов последовательности X1,…,Xn по убыванию.

7. Реализовать алгоритм сортировки бинарными вставками для сортировки элементов последовательности X1,…,Xn . Повторные вхождения элементов игнорировать.

8. Рассмотрим два алгоритма выбора наименьшего из n неравных чисел. Первый алгоритм: найти меньшее из первых двух чисел и сравнив его с третьим опять взять меньшее, сравнить с четвертым и т.д. Второй алгоритм («Кубковая система»): разбить числа на пары, меньшее из каждой пары пропустить в следующий тур. В следующем туре повторить тоже самое и т.д. пока не останется одно число. Сравнить количество сравнений в каждом из алгоритмов.

9. Пусть имеются данные о набранных очках каждого спортсмена в шахматном турнире. Используя «кубковую систему» (см.зад.5) вывести фамилию победителя на экран.

10. Имеются данные о баллах, набранных за годы учебы каждым студентом. Составить список студентов на распределение (чем выше баллы, тем раньше идет распределение). Упорядочивание осуществить методом простых вставок.

11 .Использовать число сравнений и число перемещений (т.е. перестановок с одного места на другое) элементов Х1,…,Xn в процессе применения алгоритмов сортировки выбором и сортировки обменами и сортировки простыми вставками. Показать, что число перемещений для алгоритма сортировки выбором ограничено некоторой линейной функцией от n.

11. (См. задачу №10) Доказать ,что число сравнений для алгоритмов сортировки выбором (например, Х1>X2>…>Xn) является квадратичной функцией от n.

12.(См. задачу №10) Доказать ,что число сравнений для алгоритмов сортировки обменами (например, Х1>X2>…>Xn) является квадратичной функцией от n.

13.(См. задачу №10) Доказать ,что число сравнений для алгоритмов сортировки простыми вставками (например, Х1>X2>…>Xn) является квадратичной функцией от n.

14.Последовательными просмотрами чисел x₁,…, x_i-1 найти наименьшее i такое, что x_i>x_i+1. Поменять x_i и x_i+1 местами и возобновить просмотр с начала массива .Когда не удается найти i массив будет упорядочен. Реализовать этот алгоритм для сортировки по возрастанию.

15. Реализовать предыдущий алгоритм для сортировки по убыванию.