Silver 16 декабря 2019

6 алгоритмов сортировки в гифках

Освежите знания алгоритмов сортировки с помощью нашей визуализированной подборки. Примеры кода на С#.

Сортировка – важный аспект программирования. Отсортированные данные позволяют быстрее и эффективнее работать с данными.

Для описания эффективности алгоритма мы использовали два основных критерия: расход памяти и асимптотическую временную сложность (О-нотация).

С асимптотической сложностью можете ознакомиться в другой нашей статье.

Bubble Sort

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

Это самый медленный из алгоритмов с квадратичной скоростью O(n2). Однако он самый легкий в реализации и не использует много памяти.

        //функцию Swap мы будем в нескольких алгоритмах. Её реализация везде идентична.
private static void  Swap(int[] arr, int i, int j)
{
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;

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

Insertion Sort

Сортировка вставками – алгоритм квадратичной сложности и тоже не злоупотребляет дополнительной памятью. Тем не менее, его средняя скорость выполнения примерно вдвое выше, чем у пузырьков.

Принцип прост. Все элементы просматриваются по очереди. Просмотренные элементы считаются отсортированными и каждый новый ставится на нужное место в ранее упорядоченной последовательности.

        public static void InsertionSort (int[] data)
{
    int i, j;
    for (j = 1; j < data.Length; j++) {
        for (i = j; i > 0 && data[i] < data[i-1]; i--) 
            Swap(data, i, i - 1);
        }
 }
    

Shell Sort

Сортировка Шелла – это та же сортировка вставками, но с предварительными грубыми проходами. Принцип похожий, но сравнение идет не соседних элементов, а нескольких в определенном интервале. Это позволяет оптимизировать перебор.

        private static void ShellSort(int[] data)
{
    int step = data.Length / 2;
    int temp;

    while (step > 0)
    {
        for (int i = 0; i + step < data.Length; i++)
        {
            int j = i + step;
            temp = data[j];

            while (j - step >= 0 && temp < data[j - step])
            {
                data[j] = data[j - step];
                j = j - step;
            }

            data[j] = temp;
        }

        step = step / 2;
    }
}
    

Quick Sort

Быстрая сортировка или сортировка Хоара является одной из самых эффективных: на случайных данных достигает производительности O(n log(n)). Однако алгоритм является рекурсивным, поэтому использует много дополнительной памяти.

Принцип интересней прошлых примеров. Сначала мы определяем опорную точку в последовательности. Теоретически это может быть любой элемент, на практике выбирают либо медианный, либо средний. Потом перераспределяем так, чтобы все элементы меньше опорного были слева, а больше – справа. Применяем алгоритм рекурсивно к обеим половинам, пока в них больше одного элемента.

        private static int Partition(int[] arr, int left, int right)
{
    int pivot = arr[left];
    while (true)
    {
        while (arr[left] < pivot)
            left++;

        while (arr[right] > pivot)
            right--;

        if (left < right)
        {
            if (arr[left] == arr[right]) return right;
                Swap(arr, left, right);
        }
        else
        {
            return right;
        }
    }
}
private static void QuickSort(int[] arr, int left, int right)
{
    if (left < right)
    {
        int pivot = Partition(arr, left, right);
        if (pivot > 1)
            QuickSort(arr, left, pivot - 1);

        if (pivot + 1 < right)
            QuickSort(arr, pivot + 1, right);
    }
}
    

Merge Sort

Сортировка слиянием похожа по принципу на быструю и тоже является рекурсивной. Скорость алгоритма O(n log(n)) и требует дополнительной памяти в размере исходной последовательности.

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

        private static int[] MergeSort(int[] array)
{
    if (array.Length == 1)
        return array;

    int middle = array.Length / 2;
//для лаконичности используем linq    
return Merge(MergeSort(array.Take(middle).ToArray()), MergeSort(array.Skip(middle).ToArray()));
}

private static int[] Merge(int[] arr1, int[] arr2)
{
    int ptr1 = 0, ptr2 = 0;
    int[] merged = new int[arr1.Length + arr2.Length];

    for (int i = 0; i < merged.Length; ++i)
    {
        if (ptr1 < arr1.Length && ptr2 < arr2.Length)
            merged[i] = arr1[ptr1] > arr2[ptr2] ? arr2[ptr2++] : arr1[ptr1++];
        else
            merged[i] = ptr2 < arr2.Length ? arr2[ptr2++] : arr1[ptr1++];
    }

    return merged;
}
    

HeapSort

Пирамидальная сортировка или сортировка кучей тоже имеет асимптотическую сложность O(n log(n)), но на практике оказывается медленнее предыдущих двух и применяется достаточно редко, хоть и не требует дополнительного выделения памяти.

Алгоритм интересен своим подходом. Принцип похож на сортировку вставками. Только мы не ищем место элемента в массиве, а просеиваем его в двоичную кучу (Heap).

Чтобы понять, почему это ускоряет процесс с n до log(n), давайте разберем, что это за структура данных. По сути, куча – бинарное дерево, которое удовлетворяет дополнительным условиям:

  1. Дерево сбалансировано. Т. е. все листья имеют глубину h или h-1, где h – это глубина дерева.
  2. Уровень h заполнен слева направо.
  3. Каждый элемент должен быть меньше или равен своего родителя, в корне – максимальный элемент.

Готовая пирамида выглядит так:

        static void HeapSort(int[] data)
{
    var length = data.Length;
    for (int i = length / 2 - 1; i >= 0; i--)
    {
        Heapify(data, length, i);
    }
    for (int i = length - 1; i >= 0; i--)
    {
        int temp = data[0];
        data[0] = data[i];
        data[i] = temp;
        Heapify(data, i, 0);
    }
}

/* Пирамиду можно строить по разному, самый оптимальный вариант - в виде массива,
где потомки элемента data[i] хранятся в ячейках a[2i+1] и a[2i+2]. 
*/
static void Heapify(int[] data, int length, int i)
{
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < length && data[left] > data[largest])
    {
        largest = left;
    }
    if (right < length && data[right] > data[largest])
    {
        largest = right;
    }
    if (largest != i)
    {
        Swap(data, i, largest);
        Heapify(data, length, largest);
    }
}
    
Существует около двух десятков сортировок, как эффективных, так и абсурдно ужасных. Какие бы вы хотели разобрать подробнее?

РУБРИКИ В СТАТЬЕ

МЕРОПРИЯТИЯ

Комментарии 0

ВАКАНСИИ

Senior Backend developer (Java)
Москва, по итогам собеседования
Senior Java developer
по итогам собеседования

ЛУЧШИЕ СТАТЬИ ПО ТЕМЕ

BUG