Компьютерный центр г. Светлогорска

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

Основная задача сортировки формулируется следующим образом: дан массив, содержащий n элементов, требуется расположить элементы в порядке неубывания. Так, ниже изображен массив до и после сортировки.

Пузырьковая сортировка

Обозначим за n длину массива и n раз пройдёмся по нему слева направо, меняя два соседних элемента, если первый больше второго. Каждую итерацию максимальный элемент «всплывает» как пузырек к концу массива – отсюда и название.

def bubble_sort(n, a):
    for j in range(n):
        for i in range(n - 1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]

Так как у нас два вложенных цикла, каждый из которых делает не более \(O(n)\) итераций, внутри которых за \(O(1)\) происходит сравнение и обмен соседних элементов, то суммарное время работы будет не более \(O(n^2)\).

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

Похожим методом является сортировка выбором (минимума или максимума). Чтобы отсортировать массив, n раз выберем минимум среди еще неотсортированных чисел и поставим его на своё место (а именно, на i-ю позицию после i-й итерации). Чтобы упростить реализацию, на i-ой итерации будем искать минимум на отрезке [i;n-1], меняя его местами с текущим i-м элементом, после чего отрезок [0;i] будет отсортирован.

def selection_sort(n, a):
    for i in range(n - 1):
        for j in range(i + 1, n):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]

После каждой из \(O(n)\) итераций мы за время \(O(n)\) получаем отсортированный префикс (первые \(i\) элементов), а значит за \(O(n^2)\) операций отсортируем весь массив целиком.

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

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

def insertion_sort(n, a):
    for i in range(1, n):
        j = i - 1
        while j >= 0 and a[j] > a[j+1]:
            a[j], a[j+1] = a[j+1], a[j]
            j -= 1

Время работы в худшем случае тоже \(O(n^2)\). Однако, в отличие от двух предыдущих квадратичных сортировок, в некоторых хороших случаях время работы может быть меньше, потому что мы добавили условие ранней остановки во внутреннем цикле. Например, алгоритм сделает \(O(n)\) операций, если массив изначально отсортирован.

Сортировка подсчётом

Все предыдущие алгоритмы работали с массивами, в которых лежат могут лежать абсолютно любые объекты, которые можно сравнивать: числа, строки, другие массивы – почти все что угодно. В особом случае, когда элементы могут принадлежать только какому-то небольшому множеству, можно использовать другой алгоритм – сортировку подсчётом.

Пусть, например, нам гарантируется, что все числа целые и лежат в промежутке от \(0\) до \(100\). Тогда есть такой простой алгоритм:

● Создадим массив размера \(101\), в котором будем хранить на i-м месте, сколько раз число i встретилось в этом массиве.

● Пройдёмся по всем числам исходного массива и увеличим соответствующее значение массива на \(1\).

● После того, как мы посчитали, сколько раз каждое число встретилось, можно просто пройтись по этому массиву и вывести \(0\) столько раз, сколько встретилась \(0\), вывести \(1\) столько раз, сколько встретилась \(1\), и так далее.

def count_sort(n, a):
    cnt = [0] * 101
    for ai in a:
        cnt[ai] += 1
  
    j = 0
    for i in range(101):
        while cnt[i] > 0:
            cnt[i] -= 1
            a[j] = i
            j += 1

Время работы такого алгоритма составляет \(O(m+n)\) где m – число возможных значений, n – число элементов в массиве. Если количество возможных различных элементов в множестве относительно невелико, то сортировка подсчётом является одним из самых оптимальных решений.

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

В Python метод list.sort() и функция sorted() эффективно сортируют данные. Например, в следующем фрагменте кода элементы списка сортируются в порядке неубывания:

a = [4, 2, 5, 3, 5, 8, 3]
a.sort()

После сортировки список будет иметь вид [2, 3, 3, 4, 5, 5, 8]. По умолчанию сортировка производится в порядке неубывания, но можно отсортировать и в порядке невозрастания:

a.sort(reverse=True)

Множество можно отсортировать следующим образом:

a = {4, 2, 3, 5, 8}
b = sorted(a)  # [2, 3, 4, 5, 8]

А ниже показано, как отсортировать строку s:

s = "monkey"
a = sorted(a)  # ['e', 'k', 'm', 'n', 'o', 'y']

Под сортировкой строки понимается расположение её символов в алфавитно порядке. Например, строка "monkey" превращается в список ['e', 'k', 'm', 'n', 'o', 'y'].

Операторы сравнения

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

В большинствве типов данных Python имеются встроенные операторы сравнения, так что элементы таких типо будут сортироваться автоматически. Числа сортируются по значениям, строки – в лексикографическом порядке. Списки сортируются сначала по первым элементам, в случае их совпадения – по вторым и т.д.

a = [
    [2, 1, 4],
    [1, 5, 3],
    [2, 1, 3],
]
a.sort()
# результат: [[1, 5, 3], [2, 1, 3], [2, 1, 4]]

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

a = ["apple", "cherry", "kiwi", "banana"]
a.sort(key=len)
# результат: ['kiwi', 'apple', 'cherry', 'banana']

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

 Для сортировки словаря по значениям с получением ключей применяется следующий код:

d = {'a': 3, 'b': 1, 'c': 2}
a = sorted(d, key=d.get)

# результат: ['b','c','a']

Можно также определить собственную функцию comp и передать её в качестве параметра key или использовать lambda-функцию:

def comp(x):
    return -(x % 10)

a = [210, 18, 103, 9, 748]

# сортировка с помощью функции comp
a.sort(key=comp)

# сортировка с помощью lambda-функции
a.sort(key=lambda x: -(x % 10))

# результат: [9, 18, 748, 103, 210]

В примере выше список сортируется по невозрастанию последней цифры.

Чтобы отсортировать список по второму элементу списка или кортежа, можно использовать следующую конструкцию:

def comp(x):
    return x[1]

a = [(1, 'b'), (2, 'a'), (0, 'c')]

# сортировка с помощью функции comp
a.sort(key=comp)

# сортировка с помощью lambda-функции
a.sort(key=lambda x: x[1])

# результат: [(2, 'a'), (1, 'b'), (0, 'c')]

Отсортировать список по нескольким полям можно следующим образом:

def comp(x):
    return x[0], x[1]

a = [('Ivan', 30), ('Anna', 25), ('Ivan', 20)]

# сортировка с помощью функции comp
a.sort(key=comp)

# сортировка с помощью lambda-функции
a.sort(key=lambda x: (x[0], x[1]))

# результат: [('Anna', 25), ('Ivan', 20), ('Ivan', 30)]

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