6. Сортировка. SelectionSort. BubbleSort. QuickSort.

1. Сортировки

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

Очень часто данные сначала сортируют, а потом с ними работают. А как отсортировать?

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

Но все не так просто! Алгоритмов сортировки на самом деле очень много. И все они работают по-разному и с разной скоростью. Более того, с некоторым набором данных быстрее отработает один вариант сортировки, а с другим – другой (причем количество элементов может быть одинаковым)!

Функция Array.Sort() использует алгоритм, так называемой быстрой сортировки, но в некоторых случаях быстрее будет работать более простой вариант. Например, вам не надо сортировать весь массив, а достаточно получить только k наибольших элементов. И если в массиве 1 000 000 элементов, а k порядка 15, то использовать быструю сортировку – не самый хороший вариант. А в том случае, когда вам надо все время поддерживать данные в отсортированном порядке постоянно добавляя новые значения, быструю сортировку вообще использовать просто плохо.

Ну и самое главное: на основе стандартных алгоритмов сортировки могут строиться алгоритмы решения самых разных задач, для которых просто необходимо понимать принципы работы сортировок и их особенности (а их очень много). Именно поэтому, если вы приходите на собеседование в IT-компанию и убедили собеседника, что основы языка вы знаете, вас очень часто начинают «гонять» именно по сортировкам.

Сортировки – это очень объемная тема, с которой мы только начнем знакомиться на данном занятии.

Например, та же функция Sort по умолчанию работает только для наборов примитивных типов, как int или string. Для сортировки наборов сложных объектов придется разобраться еще и с компараторами (интерфейс IComparable), но это уже совсем другая история для другого занятия.

Итак, начинаем.

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

Посмотрите на скорость работы разных сортировок на рандомных массивах данных. Из этих сортировок мы сегодня познакомимся с четырьмя: SelectionSort (сортировка выбором), BubbleSort (пузырьковая сортировка), InsertionSort (сортировка вставками), QuickSort (быстрая сортировка).

2. SelectionSort (сортировка выбором)

На массиве из n элементов имеет время выполнения О(n2). Медленная сортировка, но ее достоинство в том, что мы постоянно увеличиваем отсортированную часть массива, то есть ее можно применять, когда нам надо, например, только k минимальных или максимальных элементов.

Шаги алгоритма:

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

Фрагмент кода программы:

private static void SelectionSort()
{
    for (int i = 0; i < _numbers.Length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < _numbers.Length; j++)
        {
            if (_numbers[j] < _numbers[min])
            {
                min = j;
            }
        }

        int temp = _numbers[i];
        _numbers[i] = _numbers[min];
        _numbers[min] = temp;
    }
}

3. BubbleSort (пузырьковая сортировка)

Сортировка простыми обменами или сортировка пузырьком (bubble sort) – простой алгоритм сортировки. Для понимания и реализации этот алгоритм - простейший, но эффективен он лишь для небольших массивов. Сложность алгоритма: О(n^2).

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

Алгоритм состоит из повторяющихся проходов по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется перестановка элементов. Проходы по массиву повторяются N-1 раз или до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает - массив отсортирован. При каждом проходе алгоритма по внутреннему циклу, очередной наибольший элемент массива ставится на своё место в конце массива рядом с предыдущим «наибольшим элементом», а наименьший элемент перемещается на одну позицию к началу массива («всплывает» до нужной позиции, как пузырёк в воде - отсюда и название алгоритма).

Фрагмент кода программы:

private static void BubbleSort()
{
    for (int i = 0; i < _numbers.Length - 1; i++)
    {
        for (int j = 0; j < _numbers.Length-1; j++)
        {
             if (_numbers[j] > _numbers[j+1])
            {
                 int temp = _numbers[j];
                 _numbers[j] = _numbers[j+1];
                 _numbers[j+1] = temp;
            }
        }
    }
}

4. InsertionSort (сортировка вставками)

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

Сортировка вставками (Insertion sort) - алгоритм сортировки, в котором элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов. Вычислительная сложность O(n^2).

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

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

Фрагмент кода программы:

private static void InsertionSort()
{
    int x;
    int j;
    for (int i = 0; i < _numbers.Length; i++)
    {
        x = _numbers[i];
        j = i;
        while (j > 0 && _numbers[j - 1] > x)
        {
            int temp = _numbers[j - 1];
            _numbers[j - 1] = _numbers[j];
            _numbers[j] = temp;
            j -= 1;
        }

        _numbers[j] = x;
    }
}

5. QuickSort (быстрая сортировка)

В большинстве случаев выполняется за О(n log n), но при очень плохом выборе опорных элементов – за О(n2).

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

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

Общая идея алгоритма состоит в следующем:

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

Сравнить все остальные элементы с опорным и переставить их в массиве так, чтобы разбить массив на три непрерывных отрезка, следующих друг за другом: «элементы меньшие опорного», «равные» и «большие».

Для отрезков «меньших» и «больших» значений выполнить рекурсивно ту же последовательность операций, если длина отрезка больше единицы.

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

Быстрая сортировка относится к алгоритмам «разделяй и властвуй».

Алгоритм состоит из трёх шагов:

• Выбрать элемент из массива. Назовём его опорным.
• Разбиение: перераспределение элементов в массиве таким образом, что элементы, меньшие опорного, помещаются перед ним, а большие или равные - после.
• Рекурсивно применить первые два шага к двум подмассивам слева и справа от опорного элемента. Рекурсия не применяется к массиву, в котором только один элемент или отсутствуют элементы.

Для выбора опорного элемента и операции разбиения существуют разные подходы, влияющие на производительность алгоритма.

Фрагмент кода программы:

private static void QuickSort(int start, int end)
{
    if (start >= end)
    {
        return;
    }

    int pivot = Partition(start, end);
    QuickSort(start, pivot - 1);
    QuickSort(pivot + 1, end);
}

private static int Partition(int start, int end)
{
    int temp;
    int marker = start;
    for (int i = start; i < end; i++)
    {
        if (_numbers[i] < _numbers[end])
        {
            temp = _numbers[marker];
            _numbers[marker] = _numbers[i];
            _numbers[i] = temp;
            marker += 1;
        }
    }

    temp = _numbers[marker];
    _numbers[marker] = _numbers[end];
    _numbers[end] = temp;
    
    return marker;
}

Вопросы к размышлению:

В каких случаях пузырьковая сортировка может быть быстрее быстрой?

Итоги занятия