Сортировки

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

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

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: Сортировка выбором

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

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

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

Ввод	Вывод
1 4 2 3 4	4 4 3 2 1

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

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

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

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

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

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

Например, вот решение задачи про сортировку в порядке неубывания в одну строку:

print(" ".join(list(map(str,sorted(list(map(int,input().split())))))))

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

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