Понятие структуры данных, алгоритма и алгоритмов сортировки

Понятие алгоритма не является чем-то контринтуитивным и знакомо многим, когда необходимо выполнить правильную последовательность действий для достижения какого-либо результата. Приготовление ужина по рецепту, наверное, — самый наглядный пример. Вместо слова «последовательность» при разговоре о компьютерных алгоритмах правильней использовать слово «порядок». Это связано с развитием приёмов многопоточного программирования. Таким образом, алгоритм — это корректно определённый порядок выполнения команд над исходными данными приводящий к формированию выходных данных. Алгоритм корректен тогда, когда для любых корректных данных результатом его работы являются корректные выходные данные. Для хранения множества однотипных данных используют структуры данных (структура данных — способ организации и хранения однотипных и/или логически связанных данных, облегчающий доступ к этим данным и их модификацию, о них речь пойдёт в других статьях).

Необходимость изучения существующих компьютерных алгоритмов связана с использованием ограниченных вычислительных ресурсов компьютера: память, процессов, скорость чтения данных с диска и запись на диск и др. Эффективность алгоритма напрямую связана с тем, сколько ресурсов компьютеру придётся затратить для решения поставленной задачи. Например, для решения задачи сортировки вставками требуется примерно c_1n^2 операций (здесь n — количество элементов данных, а c_1 — независящая от этих данных константа). Для сортировки слиянием требуется уже порядком c_2n\lg n операций (здесь \lg n — краткая запись \log_2n, а c_2 — некоторая другая константа). Скорость работы второго алгоритма выше, а наглядный пример приводит Кормэн в книге «Алгоритмы. Построение и анализ» (стр.: 34):

…рассмотрим два компьютера — А и Б. Компьютер А более быстрый, и на нём работает алгоритм сортировкой вставкой, а компьютер Б более медленный, и на нём работает алгоритм методом слияния. Оба компьютеры должны выполнить сортировку множества, состоящего из десяти миллионов чисел. (…) Предположим, что компьютер А выполняет десять миллиардов команд в секунду, а компьютер Б — только 9 миллионов команд в секунду, так что компьютер А в тысячу раз быстрее компьютера Б. Чтобы различие стало ещё большим, предположим, что код для метода вставок (т.е. для компьютера А) написан лучшим в мире программистом на машинном языке и для сортировке n чисел надо выполнить 2n^2 команд. Сортировка же методом слияния (на компьютере Б) выполнена программистом-середнячком с помощью языка высокого уровня. При этом компилятор оказался не слишком эффективным, и в результате получился код, требующий выполнения 50n\lg n команд. Для сортировки десяти миллионов чисел компьютера А понадобиться: \frac{2 * (10^7)^2}{10^{10}} = 20 000 секунд (более 5,5 часов), в то время как компьютеру Б потребуется \frac{50 * 10^7\lg 10^7}{10^7} \approx 1163 секунд (менее 20 минут).

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

Алгоритмы сортировки *

Алгоритмы сортировки — это алгоритмы, которые берут некоторую последовательность из n элементов a_1, a_2,..., a_n и переставляют элементы таким образом, чтобы получившаяся последовательность a'_1,a'_2,...,a'_n удовлетворяла условию: a'_1 \leqslant a'_2 \leqslant ... \leqslant a'_n.

Визуализация алгоритмов сортировки

  1. sorting.at
  2. toptal.com

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

Визуализация | Худшее время: O(n^2) | Лучшее время: O(n) | В среднем: O(n^2) | Требует памяти: O(n)

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

Вот алгоритм на псевдокоде:

for j = 2 to A.length do 
    value = A[j]
    i = j - 1
    while i >= 0 and A[i] > value do 
        A[i + 1] = A[i]
        A[i] = value
        i = i - 1
    end while
end for

Утверждение, что в начале каждой итерации цикла оператора for, подмассив A[1..j − 1], которые раньше находились в этом подмассиве, состоит из тех же элементов, но теперь в отсорированном порядке, называется инвариантом цикла. Инварианты позволяют понять, корректно ли работает алгоритм, и обладают 3-мя свойствами:

  1. Инициализация. Справедливы перед первой итерации цикла.
  2. Сохранение. Если они истины перед очередной итерации цикла, то остаются истинными и после неё.
  3. Завершение. Позволяют убедится в правильности алгоритма по завершению цикла.

Разберём это определение инвариантов на примере приведённого выше алгоритма:

  1. Инициализация. Перед первой итерации, когда j = 2, подмассив A[1..j − 1] состоит из единственного элемента A[1], что является тривиальным случаем, и, очевидно, такой подмассив отсортирован.
  2. Сохранение. На каждом последующем этапе осуществляется сдвиг элементов A[j − 1], A[j − 2] и т.д. на одну позицию вправо, освобождая место для A[j] элемента до тех пор, пока не найдётся подходящее место для него. После завершения итерации подмассив A[1..j] состоит из тех же элементов в отсортированном порядке.
  3. Завершение. Цикл завершается в том случае, когда j ≥ n, где n — количество элементов в исходном массиве. Поскольку подмассив A[1..j], который по существу является теперь подмассивом A[1..n] отсортирован, а подмассив A[1..n] и есть исходный массив A, то приведённый алгоритм работает правильно.

Важная особенность работы этого алгоритма заключается в том, что при уже отсортированных исходных данных цикл while не будет выполняться вовсе, т.к. проверка условия A[i] > value будет срабатывать сразу. Это позволяет алгоритму выполнить не c_1n^2 команд, а только c_2n, чем пользуются другие, более сложные алгоритмы.

Сортировка методом слияния

Визуализация | Худшее время: O(n \lg n) | Лучшее время: O(n \lg n) | В среднем: O(n \lg n) | Требует памяти: O(n)

Многие алгоритмы имеют рекурсивную структуру: для решения поставленной задачи они вызывают сами себя несколько раз, решая вспомогательные подзадачи. Обычно, разбиение происходит на подзадачи, сходные с исходной, но имеющим меньший объём. Далее они рекурсивно решаются, после чего полученные решения комбинируются для получения решения исходной задачи. Такой подход к решению задачи называется методом «разделяй и властвуй». Этот метод включает в себя 3 пункта:

  1. Разделение задачи на несколько подзадач, которые представляют собой меньшие экземпляры той же задачи.
  2. Властвование над подзадачами путём их рекурсивного решения. Если размер задач становится достаточно мал, то они может быть решена непосредственно.
  3. Комбинирование решений подзадач в решение исходной задачи.

Типичный пример этого метода — сортировка методом слияния, суть которой заключается в следующем:

  1. Разделение n-элементной сортируемой последовательности на две подпоследовательности по n / 2 элементов.
  2. Рекурсивная сортировка подпоследовательностей с использованием сортировки методом слияния.
  3. Соединение 2-х отсортированных подпоследовательностей для получение окончательного осторированного ответа.

Рекурсия останавливается тогда, когда длина соритруемой подпоследовательности становится равной 1, поскольку любая такая последовательность уже является отсортированной (тривиальный случай). Главной операцией является объединение двух осторированных последовательностей в ходе комибинирования. Её суть заключается в том, что из двух отсортированных последовательностей выбираются элементы в порядке их возрастания. Поскольку каждая из последовательностей уже отсортирована, то выбор осуществляется между 2-я значениями из разных подпоследовательностей, после чего наименьшее значение перемещается из своей подпоследовательности в комбинируемую.

Алгоритм на псевдокоде:

Merge-Sort(A, p, r)
    if p < r
        q =  ⌊(p + r) / 2⌋
        Merge-Sort(A, p, q)
        Merge-Sort(A, q + 1, r)
        Merge(A, p, q, r)

Merge(A, p, q, r)
    n1 = q - p + 1
    n2 = r - q

    L[1..n1 + 1] и R[1..n2 + 1] — новые массивы
    for i = 1 to n1
        L[i] = A[p + i - 1]
    for j = 1 to n2
        R[j] = A[q + j]
    L[n1 + 1] = ∞
    R[n2 + 1] = ∞
    i = 1
    j = 1
    for k = p to r
        if L[i] <= R[j]
            A[k] = L[i]
            i = i + 1
        else 
            A[k] = R[j]
            j = j + 1


...продолжение следует.

* здесь можно найти реализации всех приведённых алгоритмов на Java

Нашли ошибку в тексте? Выделите ошибку в тексте и нажмите Ctrl + Enter на любой странице сайта.

Сообщить об опечатке

Текст, который будет отправлен нашим редакторам: