Обзор и тестирование методов сортировки. Часть I

На днях в комментариях вконтакте у меня возник спор с одним из других студентов проекта. Суть спора заключалась в том, «кто кого» — метод sort() из класса java.util.Arrays или самописные реализации простых алгоритмов: bubble (пузырьковая), insertion (вставками), selection (выбором), shell (алгоритм Шелла). Для некоторых ответ на данный вопрос может быть очевиден, но раз спор возник, при том что у каждой из сторон были «уважаемые источники» в пользу своей точки зрения, было принято решение провести исследование, поразмяв в процессе серое вещество, реализуя различные алгоритмы. TL;DR: java.util.Arrays.sort() безоговорочно лидирует на массивах от 100 000 элементов, при меньшем размере с ним иногда может потягаться метод Шелла. Остальные рассмотренные алгоритмы сливают вчистую и могут быть полезны лишь при каких-то экзотических условиях. Теперь давайте рассмотрим, как же осуществляется сортировка массивов в наших убер-девайсах из кремния.

Selection sort. Сортировка выбором

Начнем с самого простого и очевидного способа. Суть его нам отлично демонстрирует Роберт Седжвик в своей видеолекции на coursera (привожу погано пережатую в gif мной анимацию оттуда): Посмотреть Пробегая по массиву с первого элемента, мы на каждом шаге ищем в правой части минимальный элемент, с которым и меняем местами текущий. В результате мы оставляем за собой окончательный вариант нашего массива в отсортированном виде. Вот код, реализующий этот алгоритм на Java:

public void sort(int[] array) {
        int n = array.length;
        for (int i = 0; i < n; i ++) {
            int minIndex = min(array, i, n - 1);
            swap(array, i, minIndex);
        }
    }

public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
public static int min(int[] array, int begin, int end) {
        int minVal = array[begin];
        int minIndex = begin;
        for (int i = begin + 1; i <= end; i++) {
            if (array[i] < minVal) {
                minVal = array[i];
                minIndex = i;
            }
        }
        return minIndex;
    }

Анализ алгоритма показывает, что необходимо на каждом проходе прошерстить весть остаток массива, то есть нам понадобится ровно N + (N-1) + (N-2) + … + 1 = N^2/2 сравнений. Таким образом, сложность алгоритма составляет O(N^2). Что же это означает? А означает это, что, увеличив количество элементов в массиве (N) в 2 раза, мы увеличим время работы алгоритма не в 2, а в 2^2 = 4 раза. Увеличив N в 10 раз, время работы увеличим в 100 раз и так далее. На моем ноутбуке 2012 года с процессором Core i3 под Ubuntu 14.4 я получил следующее время работы:

Insertion sort. Сортировка вставками

Здесь идея несколько иная. Опять же, обратимся к анимации от Доктора Седжвика: Посмотреть То, что впереди, нами еще даже не просмотрено, а все что оставляем позади себя, всегда остается выстроенным по порядку. Суть в том, что каждый новый элемент исходного массива мы «возвращаем» к началу до тех пор, пока он не «упрется» в меньший элемент. Таким образом, у нас опять N проходов (для каждого элемента исходного массива), но в каждом проходе в большинстве случаев мы просматриваем не весь остаток, а только часть. То есть вариант 1 + (N-1) + (N-2) + … + N = N^2/2 мы получим, только если каждый следующий элемент нам придется возвращать к самому началу, то есть в случае отсортированного «наоборот» входного массива (не везет, так невезет). В случае же уже отсортированного массива (вот везуха ваще) будет полная халява – на каждом проходе всего одно сравнение и оставление элемента на месте, то есть отработает алгоритм за время, пропорциональное N. Сложность алгоритма же будет определяться худшим теоретическим случаем, то есть O(N^2). Среднестатистически же, время работы будет пропорционально N^2/4, то есть, вдвое быстрее предыдущего алгоритма. В моей реализации из-за неоптимального использования перестановки время работы получилось больше, чем у Selection. Планирую в ближайшее время исправить и обновить пост. Вот код и результат его работы на той же машине:

public void sort(int[] array) {
        int length = array.length;
        for (int i = 1; i < length; i++) {
            for (int j = i; j >= 1; j--) {
                if (array[j] < array[j - 1])
                    swap(array, j, j - 1);
                else
                    break;
            }
        }
    }

Shell sort. Сортировка Шелла

Умный мужик Дональд Шелл аж в 1959-м году заметил, что в алгоритме вставками дороже всего обходятся случаи, когда элемент возвращается очень далеко к началу массива: на каком-то проходе мы вернем элемент к началу на пару позиций, а на другом проходе почти через весь массив к началу – далеко и долго. Нельзя ли это сделать сразу, прыгая через несколько элементов? И такой способ он нашел. Заключается он в последовательном выполнении особых частичных сортировок, называемых в общем виде d-sort или, у Седжвика, h-sort (подозреваю, h означает hop - прыжок). 3-sort, например, будет сравнивать рассматриваемый элемент не с предыдущим, а пропустит два и сравнит с отстоящим на 3 позиции назад. Если поменяли, он его сравнит снова с элементом на 3 позиции назад и так далее. Суть в том, что полученный в результате массив будет «3-отсортирован», то есть неправильность положения элементов составит менее 3х позиций. Работать с таким алгоритму вставки будет легко и приятно. Кстати, «1-sort» является ничем иным, как просто алгоритмом вставки=) Последовательно применяя к массиву h-sort с уменьшающимся значением h, мы сможем отсортировать большой массив быстрее. Вот как это выглядит: Посмотреть Сложность здесь заключается в том, как выбрать правильную последовательность частичных сортировок. От этого, в итоге, зависит производительность алгоритма. Наиболее распространенной является последовательность, предложенная Дональдом Кнутом: h = h*3 + 1, то есть 1, 4, 13, 40, … и так до 1/3 размера массива. Такая последовательность обеспечивает достойную производительность, а также проста в реализации. Анализ алгоритма требует тонн матана и мной не осилен. Обширность анализа так же определяется множеством вариантов последовательностей h. Эмпирически же можно сказать, что скорость алгоритма весьма хороша – смотрите сами: Миллион элементов менее, чем за секунду! А вот код на Java с кнутовской последовательностью.

public void sort(int[] array) {
        int h = 1;
        while (h*3 < array.length)
            h = h * 3 + 1;

        while(h >= 1) {
            hSort(array, h);
            h = h/3;
        }
    }

    private void hSort(int[] array, int h) {
        int length = array.length;
        for (int i = h; i < length; i++) {
            for (int j = i; j >= h; j = j - h) {
                if (array[j] < array[j - h])
                    swap(array, j, j - h);
                else
                    break;
            }
        }
    }

Bubble sort. Метод пузырька

Это классика! Этот алгоритм реализует почти каждый начинающий программист. Это настолько классика, что у Доктора Седжвика даже не нашлось анимации для него, потому мне пришлось потрудиться самому. Посмотреть Здесь на каждом проходе мы обходим массив с начала до конца, меняя местами соседние элементы, стоящие не по порядку. В результате самые крупные элементы «всплывают» (отсюда и название) в конец массива. Каждый новый проход мы начинаем, оптимистично надеясь, что массив уже отсортирован (sorted = true). В конце прохода, если мы видим, что ошиблись, начинаем новый проход. Сложность здесь заключается в том, что мы, опять же, обходим весь (почти) массив на каждом проходе. Сравнение происходит на каждом шаге, обмен - почти на каждом, что делает данный алгоритм одним из самых медленных (если рассматривать рационально реализованные, а не "сортировку встряхиванием" и прочие подобные). Интересно, что формально сложность и здесь будет равна O(N^2), только вот коэффициент гораздо выше, чем у вставок и выборов. Код алгоритма:

public void sort(int[] array) {
        boolean isSorted;
        int nMinusOne = array.length - 1;
        for(int i = 0; i < nMinusOne; i++) {
            isSorted = true;
            for (int j = 0; j < nMinusOne - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSorted = false;
                }
            }
            if (isSorted)
                return;
        }
    }

Время работы: Почувствуйте разницу: более получаса на миллионе элементов! Вывод: Никогда не исползуйте этот алгоритм!!!

Резюме первой части

Как итог предлагаю посмотреть общую таблицу для этих алгоритмов. Можете так же сравнить с результатами для встроенного метода java.util.Arrays.sort(). Похоже на какую-то магию — что же может быть быстрее Шелла? Об этом напишу в следующей части. Там мы рассмотрим широко применяемые алгоритмы быстрой сортировки, а также сортировки слиянием, узнаем о разнице в методах сортировки массивов из примитивов и ссылочных типов, а также познакомимся с очень важным в этом деле интерфейсом Comparable ;) Ниже можете изучить график, построенный в логарифмическом масштабе по данным таблицы. Чем более полого идет линия, тем лучше алгоритм =) Кто хочет скачать весь проект и прогнать тесты у себя, держите ссылку: Java До встречи в следующей части! =)