Сортировки

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

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

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] добавляется в отсортированную часть списка.

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

Ввод	Вывод
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)