#111156

Сортировка выбором

Темы: [Сортировка выбором (максимума)]

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

Решите эту задачу при помощи алгоритма сортировки выбором.Решение оформите в виде функции SelectionSort(A).

В алгоритме сортировки выбором мы находим наибольший элемент в списке и ставим его на первое место, затем находим наибольший элемент из оставшихся и ставим его на второе место и т.д.

Примеры

Входные данные

1 4 2 3 4

Выходные данные

4 4 3 2 1

#111157

Сортировка вставкой

Темы: [Сортировка вставками]

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

Решите эту задачу при помощи алгоритма сортировки вставкой.Решение оформите в виде функции InsertionSort(A).

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

В алгоритме сортировки вставкой в каждый произвольный момент начальная часть массива уже отсортирована. В решении имеется цикл for i in range(1, len(A)), внутри которого предположении, что элементы списка A[0],A[1], ..., A[i-1]уже отсортированы, элемент A[i]добавляется в отсортированную часть списка.Для этого находится позиция, в которую необходимо вставить элемент A[i], затем осуществляется циклический сдвиг фрагмента уже отсортированной части.

Примеры

Входные данные

1 4 2 3 4

Выходные данные

1 2 3 4 4

#111158

Сортировка пузырьком

Темы: [Сортировка "пузырьком"]

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

Решите эту задачу при помощи алгоритма пузырьковой сортировки.Решение оформите в виде функции BubbleSort(A).

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

Вспомогательным списком пользоваться нельзя.

Примеры

Входные данные

1 4 2 3 4

Выходные данные

4 4 3 2 1

#111160

Обувной магазин

Темы: [Использование сортировки]

В обувном магазине продается обувь разного размера.Известно, что одну пару обуви можно надеть на другую,если она хотя бы на три размера больше. В магазин пришел покупатель.Требуется определить, какое наибольшее количество пар обуви сможет предложить ему продавец так, чтобы он смог надеть их все одновременно.

Входные данные

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

Выходные данные

Выведите единственное число — максимальное количество пар обуви, которое сможет надеть покупатель.

Примеры

Входные данные

60
60 63

Выходные данные

Входные данные

26 
30 35 40 41 42

Выходные данные

#111161

Результаты олимпиады (2)

Темы: [Использование сортировки]

В олимпиаде участвовало \(N\) человек. Каждый получил определенное количество баллов, при этом оказалось,что у всех участников — разное число баллов.

Упорядочите список участников олимпиады в порядке убывания набранных баллов.

Входные данные

Программа получает на вход число участников олимпиады \(N\). Далее идет \(N\) строк, в каждой строке записана фамилия участника, затем, через пробел, набранное им количество баллов.

Выходные данные

Выведите список участников (только фамилии) в порядке убывания набранных баллов.

Примеры

Входные данные

3
Ivanov 15
Petrov 10
Sidorov 20

Выходные данные

Sidorov
Ivanov
Petrov