Сортировки

Необходимо знать следующие алгоритмы сортировки: сортировка выбором (задача E), сортировка вставкой (задача F), сортировка пузырьком (задача G), сортировка целых чисел подсчетом (задача R).

Передача списка в качестве параметра

При передаче списка в функцию, например, так:

def Sort(A)

можно модифицировать элементы списка при помощи присваиваний A[i] = ..., методов pop, append, insert и т.д. Это не считается модификацией списка, как целого, т.е. имя A по-прежнему указывает на тот же список, при этом содержимое списка меняется.

Копирование списков

Присваивание B = A не создает новый список, а всего лишь делает B ссылкой на уже существующий список. Для создания копии списка можно использовать срезы:

B = A[:]

или использовать функцию copy из одноименного модуля:

from copy import *
B = copy(A)

Упражнения

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

Во многих задачах этого листка (если не оговорено иное) нельзя использовать вспомогательные списки.

A: Возрастает ли список?

Дан список. Определите, является ли он монотонно возрастающим (то есть верно ли, что каждый элемент этого списка больше предыдущего).

Выведите YES, если список монотонно возрастает и NO в противном случае.

Решение оформите в виде функции IsAscending(A). В данной функции должен быть один цикл while, не содержащий вложенных условий и циклов — используйте схему линейного поиска.

1 7 9

YES

B: k-е вхождение

Дан список чисел, число \(a\) и натуральное число \(k\) . Выведите индекс \(k\)-го по счету появления в массиве числа \(a\). Если число \(a\) встречается в массиве менее \(k\) раз, выведите число -1.

Решение оформите в виде функции KthAppearance(A, a, k).

Алгоритм решения должен быть схемой линейного поика — идем по списку пока не появится \(k\)-e по счету появление элемента \(a\). Нельзя пользоваться break, return внутри цикла, а также использовать высокоуровневые возможности списков, типа срезов, методов count, find и т.д.

1 2 1 3 2 3 2 3 2 2
3 2

5

1 1 1 1
1 5

-1

C: Количество цифр

Дана последовательность чисел, состоящая только из чисел 1, ..., 9. Последовательность завершается числом 0. Каждое число записано в отдельной строке.

Подсчитайте, сколько раз в этой последовательности встречаются значения 1, 2, ..., 9. Сохранять всю последовательность введенных чисел в списке нельзя.

Программа должна вывести ровно 9 чисел: количество единиц, двоек, ..., девяток в данной последовательности.

1
2
3
4
5
1
1
1
2
2
0

4 3 1 1 1 0 0 0 0

D: Противоположные элементы

Дан список чисел. Определите, есть ли в нем два противоположных (то есть дающих в сумме 0) числа.

Если такие числа есть в списке, выведите их индексы в порядке возрастания. Если таких чисел в списке нет, выведите одно число 0.

Срезы, операции типа in, методы типа find, index использовать нельзя.

1 2 3 -2 -4

1 3

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

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

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

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

В этой задаче разрешается модифицировать исходный список, в частности, удалить из списка i-й элемент можно при помощи метода pop(i), и использовать новый список для добавления в него элементов.

1 4 2 3 4

4 4 3 2 1

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

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

Решите эту задачу при помощи алгоритма сортировки вставкой. Решение оформите в виде функции 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

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

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

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

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

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

1 4 2 3 4

4 4 3 2 1

Функция sorted и метод sort

Функция sorted получает в качестве аргумента список, и возвращает ссылку на новый список, содержащий те же элементы в порядке возрастания. Пример:

A = [1, 6, 2, 5, 3, 4]
B = sorted(A)

Метод sort применяется к списку и переставляет элементы списка в порядке возрастания. Пример:

A.sort()

У функции sorted и метода sort есть параметр reverse. Если этот параметр установить в True, то сортировка будет выполняться в порядке невозрастания. Пример:

B = sorted(A, reverse = True)
A.sort(reverse = True)

Сортировать можно списки, элементы которых можно сравнивать между собой. Например, можно сортировать списки чисел (арифметическое сравнение), списки строк (лексикографическое сравнение), списки, элементами которых являются кортежи или списки (также лексикографическое сравнение).

Кроме того, стандартная функция и метод сортировки могут использовать для сравнения элементов списка заданные программистом функции. То есть алгоритм сортировки при сравнении элементов x[i] и x[j] будет сравнивать значения f(x[i]) и f(x[j]), где f — заданная в программе функция. Ниже приведено несколько примеров.

1.

def CmpItem1(item):
    return item[1]

A = [(1, 0), (2, 0), (1, 1), (2, -3), (2, 4), (99, -88)]
A.sort(key = CmpItem1) # сортировка по второму элементу кортежа

2.

def CmpSumDigits(item):
    s = 0
    while item > 0:
        s += item % 10
        item //= 10
    return s

A = [909, 435, 99, 23, 10000001, 369]
A.sort(key = CmpSumDigits)

Во всех последующих задачах при необходимости использовать сортировку лучше использовать стандартные алгоритмы сортировки.

Упражнения

H: Сортировка в одну строчку

Дан список чисел. Отсортируйте их в порядке невозрастания. Решение должно быть программой из одной строки, используйте в решении функцию sorted.

1 10 100 2 20 200

200 100 20 10 2 1

I: Создание архива

Системный администратор вспомнил, что давно не делал архива пользовательских файлов. Однако, объем диска, куда он может поместить архив, может быть меньше чем суммарный объем архивируемых файлов.

Известно, какой объем занимают файлы каждого пользователя.

Напишите программу, которая по заданной информации о пользователях и свободному объему на архивном диске определит максимальное число пользователей, чьи данные можно поместить в архив, при этом используя свободное место как можно более полно.

Программа получает на вход в одной строке число S  размер свободного места на диске, и число N — количество пользователей, после этого идет N чисел — объем данных каждого пользователя, записанных каждое в отдельной строке.

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

Используйте стандартную сортировку. Решение должно иметь сложность стандартной сортировки + O(N). Решение не должно модифицировать исходный список после считывания и сортировки.

100 2
200
50

1

100 3
50
30
50

2

J: Такси

После затянувшегося совещания директор фирмы решил заказать такси, чтобы развезти сотрудников по домам. Он заказал N машин —ровно столько, сколь у него сотрудников. Однако когда они подъехали, оказалось, что у каждого водителя такси свой тариф за 1 километр.

Директор знает, какому сотруднику сколько километров от работы до дома (к сожалению, все сотрудники живут в разных направлениях, поэтому нельзя отправить двух сотрудников на одной машине). Теперь директор хочет определить, сколько придется заплатить за перевозку всех сотрудников. Естественно, директор хочет заплатить как можно меньшую сумму.

В первой строке записаны N чисел через пробел, задающих расстояния в километрах от работы до домов сотрудников компании. Во второй строке записаны N чисел — тарифы за проезд одного километра в такси.

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

10 20 30
50 20 30

1700

K: Скидки

В супермаркете проводится беспрецедентная акция – «Покупая два любых товара, третий получаешь бесплатно*», а внизу мелким шрифтом приписано «* - из трех выбранных вами товаров оплачиваются два наиболее дорогих».

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

Программа получает на вход число N (1≤N≤1000), а затем N чисел – стоимости выбранных Васей товаров. Все стоимости – натуральные числа, не превышающие 10000.

Выведите одно число – сумму денег, которую Вася должен взять с собой в супермаркет (минимально возможную).

6
1 5 4 3 5 7

19

5
3 15 25 8 8

51

L: Количество различных чисел

Дан список чисел. Определите, сколько в нем различных чисел.

Решение должно иметь сложность встроенной сортировки + O(n).

1 7 9 7 1

3

M: Два ближайших числа

Дан список чисел (содержащий не менее двух элементов). Найдите в нем два ближайших друг к другу числа (то есть два числа с наименьшей разностью).

Выведите эти числа в порядке неубывания.

Решение должно иметь сложность встроенной сортировки + O(n).

9 4 1 6

4 6

N: Строительство магазина

В некотором городе на прямой улице расположено \(n\) домов. \(i\)-й дом задан неотрицательной величиной \(x_i\) — расстоянием от начала улицы до дома, таким образом, расстояние между двумя домами \(i\) и \(j\) равно \(|x_i-x_j|\).

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

Программа получает на вход список различных неотрицательных чисел — координаты домов и должна вывести координату дома, в котором необходимо открыть магазин.

1 2 3 4

2

O: Свадьбы

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

Первая строка входных данных содержит \(N\) чисел \(X_1\), ..., \(X_N\) — размеры состояний поклонников. Вторая строка содержит одно число \(Y\) — состояние девушки.

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

5 10
5

7.5

1 3 2
0

2.125

1
2

2.0

P: Выборы в США

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

Все избиратели делятся на \(K\) групп (необязательно равных по численности), каждая группа имеет одного представителя в коллегии выборщиков. Сначала в каждой группе проводится голосование по поставленному вопросу, если строго более половины избирателей группы высказывается “за”, то представитель этой группы в коллегии выборщиков голосует ”за“ от имени всей группы. Решение принимается, если строго более половины выборщиков (то есть групп) проголосовали “за”.

При такой системе решение может быть принято коллегией выборщиков, даже если “за” высказалось менее половины от общего числа избирателей.

Программа получает на вход \(K\) чисел — размеры групп.

Программа должна вывести минимальное количество избирателей, которое могло проголосовать “за”, если в итоге решение было принято коллегией выборщиков.

5 5 7

6

4 2 1 3 7

5

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

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

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

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

60
60 63

2

35
30 40 35 42 35

2

R: Коньки

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

Первая строка содержит список натуральных чисел  размеры коньков. Вторая строка содержит список размеров ног школьников.

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

41 40 39 42
42 41 42

2

S: Субботник

В классе учатся \(N\) человек. Классный руководитель получил указание разбить их на \(R\) бригад по \(C\) человек в каждой и направить на субботник (\(N = RC\)).

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

Числом неудобства бригады будем называть разность между ростом самого высокого и ростом самого низкого членов этой бригады (если в бригаде только один человек, то эта разница равна 0). Классный руководитель решил сформировать бригады так, чтобы максимальное из чисел неудобства сформированных бригад было минимально. Помогите ему в этом!

Рассмотрим следующий пример. Пусть в классе 8 человек, рост которых в сантиметрах равен 170, 205, 225, 190, 260, 130, 225, 160, и необходимо сформировать две бригады по четыре человека в каждой. Тогда одним из вариантов является такой:

1 бригада: люди с ростом 225, 205, 225, 260.

2 бригада: люди с ростом 160, 190, 170, 130.

При этом максимальное число неудобства будет во второй бригаде, оно будет равно 60, и это наилучший возможный результат.

Первая строка входных данных содержит два натуральные числа \(R\) и \(C\) — количество бригад и количество человек в каждой бригаде. Далее вводятся \(N = RC\) целых чисел по одному числу в строке — рост каждого из \(N\) учеников.

Выведите одно число — наименьшее возможное значение максимального числа неудобства сформированных бригад.

2 4
170
205
225
190
260
130
225
160

60

T: Результаты олимпиады

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

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

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

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

Указание. Создайте список, элементами которого будет кортеж: количество баллов и фамилия участника.

3
Ivanov 15
Petrov 10
Sidorov 20

Sidorov
Ivanov
Petrov

U: Личные дела

Однажды, неловкая секретарша перепутала личные дела учащихся. Теперь их снова необходимо упорядочить сначала по классам, а внутри класса по фамилиям.

В первой строке входных данных записано число \(N\) (\(1 \le N \le 1000\)) – количество личных дел. Далее записано \(N\) строк, каждая из которых состоит из фамилии учащегося (строка без пробелов) и номера класса (целое число от 1 до 11).

Нужно вывести список всех учащихся, сначала выводя номер класса, затем — фамилию учащегося. Список должен быть отсортирован по классу, а затем по фамилии.

Указание: составьте список из кортежей: номер класса и фамилия участника.

3
Ivanov 10
Petrov 9
Sidorov 9

9 Petrov
9 Sidorov
10 Ivanov

V: Сортировка дробей

В этой задаче вам нужно научиться сортировать не числа, а рациональные дроби. Программа получает на вход \(N\) дробей: сначала задается число \(N\), потом идет \(N\) строк, в каждой из которых записана одна дробь. Дробь записана в виде \(a/b\), где \(a\) и \(b\) —натуральные числа.

Программа должна вывести список этих дробей в порядке неубывания. Если в списке есть две равные дроби \(a/b=c/d\), то раньше выводится дробь, у которой меньше числитель.

Указание. Составьте список из кортежей (a / b, a, b).

3
4/2
2/6
1/2

2/6
1/2
4/2

W: Антон решает задачи

Мальчик Антон решает вступительную работу в летний математический лагерь. В ней \(N\) заданий, которые можно выполнять в произвольном порядке. Разные задачи требуют разного времени для решения в зависимости от их сложности. Пусть сложность \(i\)-го задания равна \(T_i\). Если задание с номером \(i\) выполнять \(j\)-м по счету, Антону потребуется \(T_i\times j\) времени: чем больше думаешь, тем больше устаешь. Например, если начать с первой задачи, а затем выполнить вторую, то потребуется \(T_1\times 1 + T_2\times2\) времени, а если выполнить сначала вторую задачу, а затем первую — то \(T_2\times 1 + T_1\times2\) . Подскажите Антону, в каком порядке нужно решать задачи, чтобы на выполнение всей работы ушло как можно меньше времени.

Программа получает на вход \(N\) целых чисел \(T_1\), \(T_2\), ..., \(T_N\) через пробел.

Требуется вывести сначала минимальное время, за которое можно решить все задачи, а затем — номера задач в том порядке, в котором их нужно решать, чтобы уложиться в это время. Если решений несколько, нужно вывести любое из них.

2 3

7
2 1

X: Такси - 2

В задаче про такси определите, на какой машине такси должен уехать каждый сотрудник.

Входные данные такие же, как в задаче “Такси”.

В первой строке программа должна вывести минимальную стоимость доставки всех сотрудников.

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

10 20 30
50 20 30

1700
1 3 2

10 20 1 30 30
3 3 3 2 3

243
5 1 3 2 4

Y: Рейтинг кавалеров

Другая симпатичная и предприимчивая девушка ищет себе идеального партнера для танцев.

Идеальный кавалер по ее представлениями должен иметь рост 180 сантиметров, поэтому прежде всего она хочет найти юношу, чей рост как можно ближе к 180 сантиметрам. Будет ли кавалер выше или ниже указанной величины, не имеет значения (то есть юноши с ростом 179 и 181 сантиметр одинаково привлекательны).

Среди всех кандидатов одного роста ей нужен кто-то, чей вес насколько это возможно, близок к 75 килограмм, но не превышает этой величины. Если же все кандидаты одного роста весят более 75 килограмм, то девушка выберет самого легкого из них.

Вам дан список кавалеров, содержащий имя партнера, его рост и вес.

Отсортируйте список по критерию привлекательности роста, при равной привлекательности роста — по привлекательности веса. При одинаковых параметрах роста и веса список должен быть отсортирован в лексикографическом порядке.

Выведите отсортированный список (только имена кавалеров).

10
George 195 110
Thomas 180 75
John 180 75
James 180 65
Andrew 165 110
Martin 170 70
William 180 77
Franklin 195 70
Benjamin 165 70
Theodore 165 80

John
Thomas
James
William
Martin
Benjamin
Franklin
Theodore
Andrew
George

Z: Большое число

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

Входные данные представляют собой одну или более строк, каждая из которых содержит последовательность цифр. Количество строк во входном файле не превышает 100, каждая строка содержит от 1 до 100 цифр. Гарантируется, что хотя бы в одной строке первая цифра отлична от нуля.

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

2
20
004
66

66220004

ZA: Белоснежка и N гномов

«Ну не гномы, а наказание какое-то!», – подумала Белоснежка, в очередной раз пытаясь уложить гномов спать. Одного уложишь – другой уже проснулся! И так всю ночь.

У Белоснежки N гномов, и все они очень разные. Она знает, что для того, чтобы уложить спать i-го гнома нужно ai минут, и после этого он будет спать ровно bi минут. Помогите Белоснежке узнать, может ли она получить хотя бы минутку отдыха, когда все гномы будут спать, и если да, то в каком порядке для этого нужно укладывать гномов спать.

Например, пусть есть всего два гнома, \(a_1 = 1, b_1 = 10, a_2 = 10, b_2 = 20\). Если Белоснежка сначала начнет укладывать первого гнома, то потом ей потребуется целых 10 минут, чтобы уложить второго, а за это время проснется первый. Если же она начнет со второго гнома, то затем она успеет уложить первого и получит целых 10 минут отдыха.

Первая строка входного файла содержит число \(n (1 ≤ n ≤ 10^5)\), вторая строка содержит числа \(a_1, a_2, ... a_n\), третья – числа \(b_1, b_2,... b_n (1 ≤ a_i, b_i ≤ 10^9)\).

Выведите в выходной файл N чисел – порядок, в котором нужно укладывать гномов спать. Если Белоснежке отдохнуть не удастся, выведите число -1.

2
1 10
10 20

2 1

2
10 10
10 10

-1