сортировка расческой c код

Сортировка расчёской

Всем привет! Помогите, пожалуйста разобрать код.

Сортировка расчёской и быстрая сортировка
В файле in.txt записана последовательность целых чисел. Заданными методами отсортировать числа и.

Сортировка «расческой»
ребят,помогите пожалуйста с сортировкой расческой. нужен пример алгоритма и блок-схема. на гугл не.

Комментарий модератора

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

Могу ли я в самом коде вместо вызова ф-ии cmp написать if (array[i + jump]> array[i]) и что я потеряю при такой замене?

Попытался написать программу целиком

The number of bytes in the array is 160
The number of bytes returned by getSize is 4

Объясните плз почему 4? Ф-ия считает размер в байтах адреса первого элемента массива?

Помощь в написании контрольных, курсовых и дипломных работ здесь.

Подсчет количества перестановок в сортировке расческой
Нужно подсчитать количество перестановок, сортируя массив «расческой» и вывести результат в.

Сортировка расческой
Добрый день Я новичок, пытаюсь разобраться с сортировкой расческой. Можете подсказать, корректен.

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

Источник

Расческа сортировка

Comb Sort — это в основном улучшение по сравнению с Bubble Sort. Пузырьковая сортировка всегда сравнивает соседние значения. Таким образом, все инверсии удаляются по одному. Comb Sort улучшает Bubble Sort, используя разрыв размером больше 1. Разрыв начинается с большого значения и уменьшается в 1,3 раза на каждой итерации, пока не достигнет значения 1. Таким образом, Comb Sort удаляет более одного подсчета инверсии с одним своп и работает лучше, чем Bubble Sort.

Эмпирически было установлено, что коэффициент сжатия равен 1,3 (при тестировании Combsort в более чем 200 000 случайных списках) [Источник: Wiki ]

Хотя в среднем он работает лучше, чем Bubble Sort, в худшем случае остается O (n 2 ).

Ниже приведена реализация.

// C ++ реализация Comb Sort
#include

using namespace std;

// Найти разрыв между элементами

int getNextGap( int gap)

// Уменьшить разрыв по коэффициенту сжатия

// Функция для сортировки [0..n-1] с использованием Comb Sort

void combSort( int a[], int n)

// Инициализировать swapped как true, чтобы убедиться, что

bool swapped = true ;

// Продолжаем работать, пока разрыв больше 1 и последний

// итерация вызвала своп

// Найти следующий пробел

// Инициализируем поменять местами как ложь, чтобы мы могли

// проверяем, произошел ли обмен

// Сравнить все элементы с текущим разрывом

int n = sizeof (a)/ sizeof (a[0]);

printf ( «Sorted array: \n» );

// Java-программа для реализации Comb Sort

// Найти разрыв между элементами

int getNextGap( int gap)

// Уменьшить разрыв по коэффициенту сжатия

// Функция для сортировки arr [] с использованием Comb Sort

// Инициализировать swapped как true, чтобы убедиться, что

boolean swapped = true ;

// Продолжаем работать, пока разрыв больше 1 и последний

// итерация вызвала своп

// Найти следующий пробел

// Инициализируем поменять местами как ложь, чтобы мы могли

// проверяем, произошел ли обмен

// Сравнить все элементы с текущим разрывом

// Поменять местами arr [i] и arr [i + gap]

public static void main(String args[])

CombSort ob = new CombSort();

System.out.println( «sorted array» );

>
/ * Этот код предоставлен Раджатом Мишрой * /

# Python программа для реализации CombSort

# Найти следующий пробел из текущего

# Сокращение разрыва по коэффициенту усадки

# Функция для сортировки arr [] с использованием Comb Sort

# Инициализируйте swapped как true, чтобы убедиться, что

# Продолжайте бегать, пока разрыв больше 1 и последний

# итерация вызвала своп

# Найти следующий пробел

# Инициализировать поменять местами как ложь, чтобы мы могли

# проверить, произошел ли обмен

# Сравнить все элементы с текущим разрывом

if arr[i] > arr[i + gap]:

arr[i], arr[i + gap] = arr[i + gap], arr[i]

# Код драйвера для проверки выше

print ( «Sorted array:» )

for i in range ( len (arr)):

# Этот код предоставлен Мохитом Кумрой

// C # программа для реализации Comb Sort

// Найти разрыв между элементами

static int getNextGap( int gap)

// Уменьшить разрыв по коэффициенту сжатия

// Функция для сортировки arr [] с использованием Comb Sort

static void sort( int []arr)

// Инициализируем поменять местами как истину

// убедитесь, что цикл работает

bool swapped = true ;

// Продолжайте работать, пока разрыв больше

// 1 и последняя итерация вызвала своп

// Найти следующий пробел

// Инициализируем поменять местами как ложь, чтобы мы могли

// проверяем, произошел ли обмен

// Сравнить все элементы с текущим разрывом

// Поменять местами arr [i] и arr [i + gap]

public static void Main()

Console.WriteLine( «sorted array» );

// Этот код предоставлен Sam007

Иллюстрация:
Пусть элементы массива будут

Первоначально значение разрыва = 10
После усадки значение разрыва => 10 / 1,3 = 7 ;

Новое значение разрыва => 7 / 1,3 = 5 ;

Новое значение разрыва => 5 / 1,3 = 3 ;

Новое значение разрыва => 3 / 1,3 = 2 ;

Новое значение разрыва => 2 / 1,3 = 1 ;

Сложность по времени: сложность этого алгоритма в наихудшем случае составляет O (n 2 ), а сложность в наилучшем случае — O (n).

Вспомогательное пространство: O (1).

Тест на расческу

Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Источник

О сортировках (пузырьковой, быстрой, расческой. )

Эта статья ориентирована в первую очередь на начинающих программистов. О сортировках вообще и об упомянутых в заголовке в интернете море статей, зачем нужно еще одна? Например, есть хорошая статья здесь, на хабре: Пузырьковая сортировка и все-все-все. Во-первых, хорошего много не бывает, во-вторых в этой статье я хочу ответь на вопросы «зачем, что, как, почему».Зачем нужны сортировки? В первую очередь, для поиска и представления данных. Некоторые задачи с неотсортированными данными решить очень трудно, а некоторые просто невозможно. Пример: орфографический словарь, в нем слова отсортированы по алфавиту. Если бы это было не так, то попробуйте найти в нем нужное слово. Телефонная книга, где абоненты отсортированы по алфавиту. Даже если сортировка не обязательна и не сильно нужна, все равно бывает удобнее работать с отсортированными данными.

Время сортировки 100001 элемента

Измерим время сортировки для массива, содержащего 100001 элемент на компьютере с процессором Intel i5 (3.3Ггц).Время указано в сек, через дробь указано количество проходов (для быстрой сортировки оно неизвестно).Как и ожидалось, шейкерная сортировка на проблемном массиве (который полностью упорядочен, только первый и последний элементы переставлены) абсолютный лидер. Она идеально «заточена» под эти данные. Но на случайных данных сортировки расческой и qsort не оставляют соперницам шанса. Пузырьковая сортировка на проблемном массиве показывает двукратное увеличение скорости по сравнению с случайным просто потому, что количество операций перестановки на порядки меньше.

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

Сравниваемые элементы показаны в зеленых рамках, а переставленные — в красных

Дополнение после публикации

Я ни коей мере не считаю qsort плохой или медленной — она достаточно быстра, функциональна и при возможности следует пользоваться именно ею. Да, ей приходится тратить время на вызов функции сравнения и она уступила «расческе», которая сравнивает «по месту». Это отставание несущественно (сравните с отставанием пузырька от qsort, которое будет увеличиваться при росте массива). Пусть теперь надо сравнивать не числа, а какую-то сложную структуру по определенному полю и пусть эта структура состоит из 1000 байтов. Поместим 100тыс элементов в массив (100мб — это кое-что) и вызовем qsort. Функция fcomp (функция-компаратор) сравнит нужные поля и в результате получится отсортированный массив. При этом при перестановке элементов qsort придется 3 раза копировать фрагменты по 1000 байтов. А теперь «маленькая хитрость» — создадим массив из 100тыс ссылок на исходные элементы и передадим в qsort начало этого массива ссылок. Поскольку ссылка занимает 4 байта (в 64 битных 8), а не 1000, то при обмене ссылок qsort надо поменять эти 4/8 байтов. Разумеется, нужно будет изменить fcomp, поскольку в качестве параметров она теперь получит не адреса элементов, а адреса адресов элементов (но это несложное изменение). Зато теперь можно сделать несколько функций сортировки (каждая сортирует по своему полю структуры). И даже, при необходимости, можно сделать несколько массивов ссылок. Вот сколько возможностей дает qsort!

Кстати: использование ссылок на объекты вместо самих объектов может быть полезно не только при вызове qsort, но и при применении таких контейнеров как vector, set или map.

Источник

Как работает сортировка расчёской

Улучшаем пузырьковую сортировку.

Продолжаем рассказывать о разных видах алгоритмов сортировок. Мы уже разобрали самую простую пузырьковую сортировку и теперь улучшаем её — пишем сортировку расчёской.

Коротко про пузырьковую сортировку

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

Если представить числа в виде столбиков, в зависимости от их размера, то пузырьковая сортировка будет выглядеть так:

Чем плоха пузырьковая сортировка

Главный недостаток пузырьковой сортировки — её скорость и полный перебор всех элементов массива. Скорость работы алгоритма зависит не от количества сравнений (они выполняются быстро), а от количества перестановок (на них как раз и тратится много процессорного времени).

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

В чём хитрость сортировки расчёской

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

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

👉 Опытным путём программисты установили оптимальное расстояние между элементами — это длина массива, поделённая на 1,247 (понятное дело, расстояние нужно округлить до целого числа). С этим числом алгоритм работает быстрее всего.

Как работает алгоритм сортировки расчёской

На первом шаге мы находим длину массива (например, 10 элементов) и делим её на 1,247. Допустим, после округления у нас получилось число 8. Теперь мы проходим первый цикл пузырьковой сортировки, только сравнивая не 1 и 2, 2 и 3, а сразу 1 и 8, 2 и 9, 3 и 10. Это отправит самые большие числа, если они есть в начале, в самый конец. Всего на первом шаге будет три сравнения.

На втором шаге мы берём число 8 из предыдущего этапа и снова делим его на 1,247, получая число 6. Теперь мы снова проходим весь массив и сравниваем так:

Уже получилось 5 перестановок и снова крупные числа улетели поближе к концу массива.

Так мы уменьшаем размер шага до тех пор, пока он не станет меньше единицы — к этому моменту массив будет полностью отсортирован.

🤔 Сортировка расчёской называется так из-за того, что мы как бы расчёсываем массив сначала широким гребнем (большой шаг), потом гребнем поменьше (шаг поменьше). В конце шаг равен единице, как в пузырьковой сортировке.

Сортировка расчёской на JavaScript

Запустите этот код в консоли браузера, чтобы посмотреть, как алгоритм шаг за шагом приводит массив в нормальный вид:

Почему это лучше пузырьковой сортировки, ведь алгоритм выглядит сложнее и в конце мы всё равно сравниваем соседние элементы?

То, что код выглядит сложнее, ничего не значит: нам нужна не оценка сложности кода, а скорость и эффективность работы.

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

Источник

Описание алгоритмов сортировки и сравнение их производительности

Вступление

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

Во многом статья посвящена тому, как написать все алгоритмы и протестировать их. Если говорить о самом программировании, то иногда могут возникнуть совершенно неожиданные трудности (во многом благодаря оптимизатору C++). Однако не менее трудно решить, какие именно тесты и в каких количествах нужно сделать. Коды всех алгоритмов, которые выложены в данной статье, написаны мной. Доступны и результаты запусков на всех тестах. Единственное, что я не могу показать — это сами тесты, поскольку они весят почти 140 ГБ. При малейшем подозрении я проверял и код, соответствующий тесту, и сам тест. Надеюсь, что статья Вам понравится.

Описание основных сортировок и их реализация

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

Сортировка пузырьком / Bubble sort

Будем идти по массиву слева направо. Если текущий элемент больше следующего, меняем их местами. Делаем так, пока массив не будет отсортирован. Заметим, что после первой итерации самый большой элемент будет находиться в конце массива, на правильном месте. После двух итераций на правильном месте будут стоять два наибольших элемента, и так далее. Очевидно, не более чем после n итераций массив будет отсортирован. Таким образом, асимптотика в худшем и среднем случае – O(n 2 ), в лучшем случае – O(n).

Шейкерная сортировка / Shaker sort

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

Сортировка расческой / Comb sort

Еще одна модификация сортировки пузырьком. Для того, чтобы избавиться от «черепах», будем переставлять элементы, стоящие на расстоянии. Зафиксируем его и будем идти слева направо, сравнивая элементы, стоящие на этом расстоянии, переставляя их, если необходимо. Очевидно, это позволит «черепахам» быстро добраться в начало массива. Оптимально изначально взять расстояние равным длине массива, а далее делить его на некоторый коэффициент, равный примерно 1.247. Когда расстояние станет равно единице, выполняется сортировка пузырьком. В лучшем случае асимптотика равна O(nlogn), в худшем – O(n 2 ). Какая асимптотика в среднем мне не очень понятно, на практике похоже на O(nlogn).

Об этих сортировках (пузырьком, шейкерной и расческой) также можно почитать здесь.

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

Создадим массив, в котором после завершения алгоритма будет лежать ответ. Будем поочередно вставлять элементы из исходного массива так, чтобы элементы в массиве-ответе всегда были отсортированы. Асимптотика в среднем и худшем случае – O(n 2 ), в лучшем – O(n). Реализовывать алгоритм удобнее по-другому (создавать новый массив и реально что-то вставлять в него относительно сложно): просто сделаем так, чтобы отсортирован был некоторый префикс исходного массива, вместо вставки будем менять текущий элемент с предыдущим, пока они стоят в неправильном порядке.

Сортировка Шелла / Shellsort

Несколько полезных ссылок:

Сортировка деревом / Tree sort

Будем вставлять элементы в двоичное дерево поиска. После того, как все элементы вставлены достаточно обойти дерево в глубину и получить отсортированный массив. Если использовать сбалансированное дерево, например красно-черное, асимптотика будет равна O(nlogn) в худшем, среднем и лучшем случае. В реализации использован контейнер multiset.

Здесь можно почитать про деревья поиска:

Гномья сортировка / Gnome sort

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

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

На очередной итерации будем находить минимум в массиве после текущего элемента и менять его с ним, если надо. Таким образом, после i-ой итерации первые i элементов будут стоять на своих местах. Асимптотика: O(n 2 ) в лучшем, среднем и худшем случае. Нужно отметить, что эту сортировку можно реализовать двумя способами – сохраняя минимум и его индекс или просто переставляя текущий элемент с рассматриваемым, если они стоят в неправильном порядке. Первый способ оказался немного быстрее, поэтому он и реализован.

Пирамидальная сортировка / Heapsort

Развитие идеи сортировки выбором. Воспользуемся структурой данных «куча» (или «пирамида», откуда и название алгоритма). Она позволяет получать минимум за O(1), добавляя элементы и извлекая минимум за O(logn). Таким образом, асимптотика O(nlogn) в худшем, среднем и лучшем случае. Реализовывал кучу я сам, хотя в С++ и есть контейнер priority_queue, поскольку этот контейнер довольно медленный.

Почитать про кучу можно здесь:

Быстрая сортировка / Quicksort

Выберем некоторый опорный элемент. После этого перекинем все элементы, меньшие его, налево, а большие – направо. Рекурсивно вызовемся от каждой из частей. В итоге получим отсортированный массив, так как каждый элемент меньше опорного стоял раньше каждого большего опорного. Асимптотика: O(nlogn) в среднем и лучшем случае, O(n 2 ). Наихудшая оценка достигается при неудачном выборе опорного элемента. Моя реализация этого алгоритма совершенно стандартна, идем одновременно слева и справа, находим пару элементов, таких, что левый элемент больше опорного, а правый меньше, и меняем их местами. Помимо чистой быстрой сортировки, участвовала в сравнении и сортировка, переходящая при малом количестве элементов на сортировку вставками. Константа подобрана тестированием, а сортировка вставками — наилучшая сортировка, подходящая для этой задачи (хотя не стоит из-за этого думать, что она самая быстрая из квадратичных).

Сортировка слиянием / Merge sort

Сортировка, основанная на парадигме «разделяй и властвуй». Разделим массив пополам, рекурсивно отсортируем части, после чего выполним процедуру слияния: поддерживаем два указателя, один на текущий элемент первой части, второй – на текущий элемент второй части. Из этих двух элементов выбираем минимальный, вставляем в ответ и сдвигаем указатель, соответствующий минимуму. Слияние работает за O(n), уровней всего logn, поэтому асимптотика O(nlogn). Эффективно заранее создать временный массив и передать его в качестве аргумента функции. Эта сортировка рекурсивна, как и быстрая, а потому возможен переход на квадратичную при небольшом числе элементов.

Сортировка подсчетом / Counting sort

Создадим массив размера r – l, где l – минимальный, а r – максимальный элемент массива. После этого пройдем по массиву и подсчитаем количество вхождений каждого элемента. Теперь можно пройти по массиву значений и выписать каждое число столько раз, сколько нужно. Асимптотика – O(n + r — l). Можно модифицировать этот алгоритм, чтобы он стал стабильным: для этого определим место, где должно стоять очередное число (это просто префиксные суммы в массиве значений) и будем идти по исходному массиву слева направо, ставя элемент на правильное место и увеличивая позицию на 1. Эта сортировка не тестировалась, поскольку большинство тестов содержало достаточно большие числа, не позволяющие создать массив требуемого размера. Однако она, тем не менее, пригодилась.

Блочная сортировка / Bucket sort

(также известна как корзинная и карманная сортировка). Пусть l – минимальный, а r – максимальный элемент массива. Разобьем элементы на блоки, в первом будут элементы от l до l + k, во втором – от l + k до l + 2k и т.д., где k = (r – l) / количество блоков. В общем-то, если количество блоков равно двум, то данный алгоритм превращается в разновидность быстрой сортировки. Асимптотика этого алгоритма неясна, время работы зависит и от входных данных, и от количества блоков. Утверждается, что на удачных данных время работы линейно. Реализация этого алгоритма оказалась одной из самых трудных задач. Можно сделать это так: просто создавать новые массивы, рекурсивно их сортировать и склеивать. Однако такой подход все же довольно медленный и меня не устроил. В эффективной реализации используется несколько идей:

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

2) Не будем запускаться из пустых блоков. Занесем индексы непустых блоков в отдельный массив и запустимся только от них.

3) Проверим, отсортирован ли массив. Это не ухудшит время работы, так как все равно нужно сделать проход с целью нахождения минимума и максимума, однако позволит алгоритму ускориться на частично отсортированных данных, ведь элементы вставляются в новые блоки в том же порядке, что и в исходном массиве.

4) Поскольку алгоритм получился довольно громоздким, при небольшом количестве элементов он крайне неэффективен. До такой степени, что переход на сортировку вставками ускоряет работу примерно в 10 раз.

Поразрядная сортировка / Radix sort

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

LSD (least significant digit):

Представим каждое число в двоичном виде. На каждом шаге алгоритма будем сортировать числа таким образом, чтобы они были отсортированы по первым k * i битам, где k – некоторая константа. Из данного определения следует, что на каждом шаге достаточно стабильно сортировать элементы по новым k битам. Для этого идеально подходит сортировка подсчетом (необходимо 2 k памяти и времени, что немного при удачном выборе константы). Асимптотика: O(n), если считать, что числа фиксированного размера (а в противном случае нельзя было бы считать, что сравнение двух чисел выполняется за единицу времени). Реализация довольно проста.

MSD (most significant digit):

На самом деле, некоторая разновидность блочной сортировки. В один блок будут попадать числа с равными k битами. Асимптотика такая же, как и у LSD версии. Реализация очень похожа на блочную сортировку, но проще. В ней используется функция digit, определенная в реализации LSD версии.

Битонная сортировка / Bitonic sort:

Идея данного алгоритма заключается в том, что исходный массив преобразуется в битонную последовательность – последовательность, которая сначала возрастает, а потом убывает. Ее можно эффективно отсортировать следующим образом: разобьем массив на две части, создадим два массива, в первый добавим все элементы, равные минимуму из соответственных элементов каждой из двух частей, а во второй – равные максимуму. Утверждается, что получатся две битонные последовательности, каждую из которых можно рекурсивно отсортировать тем же образом, после чего можно склеить два массива (так как любой элемент первого меньше или равен любого элемента второго). Для того, чтобы преобразовать исходный массив в битонную последовательность, сделаем следующее: если массив состоит из двух элементов, можно просто завершиться, иначе разделим массив пополам, рекурсивно вызовем от половинок алгоритм, после чего отсортируем первую часть по порядку, вторую в обратном порядке и склеим. Очевидно, получится битонная последовательность. Асимптотика: O(nlog 2 n), поскольку при построении битонной последовательности мы использовали сортировку, работающую за O(nlogn), а всего уровней было logn. Также заметим, что размер массива должен быть равен степени двойки, так что, возможно, придется его дополнять фиктивными элементами (что не влияет на асимптотику).

Timsort

Гибридная сортировка, совмещающая сортировку вставками и сортировку слиянием. Разобьем элементы массива на несколько подмассивов небольшого размера, при этом будем расширять подмассив, пока элементы в нем отсортированы. Отсортируем подмассивы сортировкой вставками, пользуясь тем, что она эффективно работает на отсортированных массивах. Далее будем сливать подмассивы как в сортировке слиянием, беря их примерно равного размера (иначе время работы приблизится к квадратичному). Для этого удобного хранить подмассивы в стеке, поддерживая инвариант — чем дальше от вершины, тем больше размер, и сливать подмассивы на верхушке только тогда, когда размер третьего по отдаленности от вершины подмассива больше или равен сумме их размеров. Асимптотика: O(n) в лучшем случае и O(nlogn) в среднем и худшем случае. Реализация нетривиальна, твердой уверенности в ней у меня нет, однако время работы она показала довольно неплохое и согласующееся с моими представлениями о том, как должна работать эта сортировка.

Подробнее timsort описан здесь:

Тестирование

Железо и система

Процессор: Intel Core i7-3770 CPU 3.40 GHz
ОЗУ: 8 ГБ
Тестирование проводилось на почти чистой системе Windows 10 x64, установленной за несколько дней до запуска. Использованная IDE – Microsoft Visual Studio 2015.

Тесты

Размер входных данных

Как проводилось тестирование

На каждом тесте было производилось 20 запусков, итоговое время работы – среднее по получившимся значениям. Почти все результаты были получены после одного запуска программы, однако из-за нескольких ошибок в коде и системных глюков (все же тестирование продолжалось почти неделю чистого времени) некоторые сортировки и тесты пришлось впоследствии перетестировать.

Тонкости реализации

Возможно, кого-то удивит, что в реализации самого процесса тестирования я не использовал указатели на функции, что сильно сократило бы код. Оказалось, что это заметно замедляет работу алгоритма (примерно на 5-10%). Поэтому я использовал отдельный вызов каждой функции (это, конечно, не отразилось бы на относительной скорости, но… все же хочется улучшить и абсолютную). По той же причине были заменены векторы на обычные массивы, не были использованы шаблоны и функции-компараторы. Все это более актуально для промышленного использования алгоритма, нежели его тестирования.

Результаты

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

Поскольку картинок очень много, они скрыты спойлерами. Немного комментариев по поводу обозначений. Сортировки названы так, как выше, если это сортировка Шелла, то в скобочках указан автор последовательности, к названиям сортировок, переходящих на сортировку вставками, приписано Ins (для компактности). В диаграммах у второй группы тестов обозначена возможная длина отсортированных подмассивов, у третьей группы — количество свопов, у четвертой — количество замен. Общий результат рассчитывался как среднее по четырем группам.

Первая группа сортировок

Массив случайных чисел

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

Частично отсортированный массив

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

Свопы

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

Изменения в перестановке

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

Повторы

Здесь все сортировки (кроме, конечно, сортировки выбором) работали почти одинаково, ускоряясь по мере увеличении количества повторов.

Итоговые результаты

За счет своего абсолютного безразличия к массиву, сортировка выбором, работавшая быстрее всех на случайных данных, все же проиграла сортировке вставками. Гномья сортировка оказалась заметно хуже последней, из-за чего ее практическое применение сомнительно. Шейкерная и пузырьковая сортировки оказались медленнее всех.

Вторая группа сортировок

Массив случайных чисел

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

Все как прежде, только Шелл с Праттом усилился на второй группе из-за отсортированности. Также становится заметным влияние асимптотики — сортировка деревом оказывается на втором месте, в отличие от группы с меньшим числом элементов.

Частично отсортированный массив

Здесь понятным образом ведут себя все сортировки, кроме Шелла с Хиббардом, который почему-то не сразу начинает ускоряться.

Здесь все, в общем, как и прежде. Даже асимптотика сортировки деревом не помогла ей вырваться с последнего места.

Свопы

Здесь заметно, что у сортировок Шелла большая зависимость от частичной отсортированности, так как они ведут себя практически линейно, а остальные две только сильно падают на последних группах.

Изменения в перестановке

Здесь все похоже на предыдущую группу.

Повторы

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

Итоговые результаты

Убедительное первое место заняла сортировка Шелла по Хиббарду, не уступив ни в одной промежуточной группе. Возможно, стоило ее отправить в первую группу сортировок, но… она слишком слаба для этого, да и тогда почти никого не было бы в группе. Битонная сортировка довольно уверенно заняла второе место. Третье место при миллионе элементах заняла другая сортировка Шелла, а при десяти миллионах сортировка деревом (асимптотика сказалась). Стоит обратить внимание, что при десятикратном увеличении размера входных данных все алгоритмы, кроме древесной сортировки, замедлились почти в 20 раз, а последняя всего лишь в 13.

Третья группа сортировок

Массив случайных чисел

Почти все сортировки этой группы имеют почти одинаковую динамику. Почему же почти все сортировки ускоряются, когда массив частично отсортирован? Обменные сортировки работают быстрее потому, что надо делать меньше обменов, в сортировке Шелла выполняется сортировка вставками, которая сильно ускоряется на таких массивах, в пирамидальной сортировке при вставке элементов сразу завершается просеивание, в сортировке слиянием выполняется в лучшем случае вдвое меньше сравнений. Блочная сортировка работает тем лучше, чем меньше разность между минимальным и максимальным элементом. Принципиально отличается только поразрядная сортировка, которой все это безразлично. LSD-версия работает тем лучше, чем больший модуль. Динамика MSD-версия мне не ясна, то, что она сработала быстрее чем LSD удивило.

Частично отсортированный массив

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

Свопы

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

Изменения в перестановке

Мне удалось достичь желаемой цели — поразрядная сортировка упала даже ниже адаптированной быстрой. Блочная сортировка оказалась лучше остальных. Еще почему-то timsort обогнал встроенную сортировку C++, хотя в предыдущей группе был ниже.

Повторы

Здесь все довольно тоскливо, все сортировки работают с одинаковой динамикой (кроме линейных). Из необычного можно заметить, что сортировка слиянием упала ниже сортировки Шелла.

Итоговые результаты

Если говорить о практическом применении, то хороша поразрядная сортировка (особенно lsd-версия), она стабильна, проста в реализации и очень быстра, однако не основана на сравнениях. Из основанных на сравнениях сортировок лучше всего смотрится быстрая сортировка. Ее недостатки — неустойчивость и квадратичное время работы на неудачных входных данных (пусть они и могут встретиться только при намеренном создании теста). Но с этим можно бороться, например, выбирая опорный элемент по какому-нибудь другому принципу, или же переходя на другую сортировку при неудаче (например, introsort, который, если не ошибаюсь, и реализован в С++). Timsort лишен этих недостатков, лучше работает на сильно отсортированных данных, но все же медленнее в целом и гораздо сложнее пишется. Остальные сортировки на данный момент, пожалуй, не очень практичны. Кроме, конечно, сортировки вставками, которую весьма удачно иногда можно вставить в алгоритм.

Заключение

Должен отметить, что не все известные сортировки приняли участие в тестировании, например, была пропущена плавная сортировка (мне просто не удалось ее адекватно реализовать). Впрочем, не думаю, что это большая потеря, эта сортировка очень громоздкая и медленная, как можно видеть, например, из этой статьи: habrahabr.ru/post/133996 Еще можно исследовать сортировки на распараллеливание, но, во-первых, у меня нет опыта, во-вторых, результаты, которые получались, крайне нестабильны, очень велико влияние системы.

Здесь можно посмотреть результаты всех запусков, а также некоторые вспомогательные тестирования: ссылка на документ.

Реализации алгоритмов с векторами остались, но их корректность и хорошую работу не гарантирую. Проще взять коды функций из статьи и переделать. Генераторы тестов тоже могут не соответствовать действительности, на самом деле такой вид они приняли уже после создания тестов, когда нужно было сделать программу более компактной.

В общем, я доволен проделанной работой, надеюсь, что Вам было интересно.

Источник