сортировка массива. какой метод сортировки массива самый быстрый и эффективный?
lol lol
что в вашем понимании считается «эффективным» методом?
для кого-то быстрота сортировки и является признаком эффективности.
а для кого-то другого под эффективностью понимается размер памяти требуемой под сортировку.
а кому-то вообще главное чтобы было сделано как можно меньше операций (и пусть оно хоть день занимает)
при все прочих равных условиях, метод «сортировки слиянием» ( у буржуев называется merge sort ) будет быстрее.
как правило, на массивах существенной длины обгоняет другой метод — «быстрый поиск» ( у буржуев зовётся QuickSort ), хотя по сложности методы имеют одинаковый порядок. Однако QuickSort может конкретно притормозить если неумело им пользоваться. В то же время QuickSort требует гараздо меньше памяти для работы, чем «сортировка слиянием»
//———————————————————————————————
template <class>
void qs(s_type *item, int left, int right)
<
/*
******Параметризированная функция быстрой сортировки массива
*/
****register int****i, j;****//для ускорения работы индексные переменные помещаем в регистры
****s_type *****x, y;****//для сортировки
//индексные переменные ставим на указанные границы массива
****i = left;****
****j = right;
//выбираем «компаранд»
****x = item[ (left+ right) / 2];
//все элементы большие компаранда переносим в левую часть массива
//все элементы меньшие компаранда переносим в правую часть массива
****do
**** <
*while(item < x && i < right) i++;
*while(x < item[j] && j > left) j—;
*if(i <= j)
* <
*****y = item;
*****item = item [j];
*****item[j] = y;
*****i++;
*****j—;
*>
****>while(i <= j);
//повторяем процедуру для отсортированных частей массива пока все не отсортируем
****if(left < j) qs(item, left, j);
****if(i < right) qs(item, i, right);
>
Как работает быстрая сортировка
Это статья о реализации одного из алгоритмов сортировки. Эти алгоритмы считаются классикой информатики: разработчиков могут спросить об этих алгоритмах на собеседовании, а сами алгоритмы помогают ощутить силу автоматики и алгоритмов. Сегодня пощупаем один из таких алгоритмов.
Ранее в статьях мы рассказали про два вида сортировки:
-
— самая простая, но медленная; — чуть сложнее, но немного быстрее.
Эти сортировки относятся к простым видам алгоритмов — надёжным, но неоптимальным по скорости и затратам памяти. Гораздо чаще вместо них используют быструю сортировку или алгоритмы на её основе — про это и будем сегодня говорить.
В чём идея быстрой сортировки
Когда в 1960 году Тони Хоар придумывал этот алгоритм, ему нужно было отсортировать данные на магнитной ленте за один проход, чтобы не перематывать плёнку много раз. Для этого он взял за основу классическую пузырьковую сортировку и преобразовал её так:
- На очередном шаге выбирается опорный элемент — им может быть любой элемент массива.
- Все остальные элементы массива сравниваются с опорным и те, которые меньше него, ставятся слева от него, а которые больше или равны — справа.
- Для двух получившихся блоков массива (меньше опорного, и больше либо равны опорному) производится точно такая же операция — выделяется опорный элемент и всё идёт точно так же, пока в блоке не останется один элемент.
Вот как это выглядит, если представить массив в виде графика:
Синяя линия — это значение опорного элемента, а серый блок показывает, какую часть массива сортирует алгоритм
Особенности алгоритма
Так как на третьем шаге мы разбиваем массив на два и для каждой части делаем то же самое, и так снова и снова, то это значит, что в нём используется рекурсия. Рекурсия — это когда функция вызывает саму себя, и при этом ей нужно держать в памяти все предыдущие этапы. Это значит, что при использовании сразу двух рекурсий (для левой и правой частей массива), может потребоваться очень много памяти. Чтобы обойти это ограничение, используют улучшенные версии быстрой сортировки — про них поговорим в другой раз.
Но несмотря на такой возможный расход памяти, у быстрой сортировки есть много плюсов:
- это один из самых быстрых алгоритмов, когда мы заранее ничего не знаем про массивы, с которыми придётся работать;
- алгоритм настолько прост, что его легко написать на любом языке программирования;
- быструю сортировку легко распараллелить и разбить на отдельные процессы;
- алгоритм работает на данных с последовательным доступом, когда мы не можем в любой момент вернуться в начало, а должны работать с данными только в одном порядке.
Выбор опорного элемента
Правильный выбор опорного элемента может сильно повысить эффективность быстрой сортировки. В зависимости от реализации алгоритма есть разные способы выбора:
- Первый элемент — в первых версиях быстрой сортировки Хоар выбирал опорным первый элемент массива. Именно так он смог обрабатывать всю магнитную ленту за один проход.
- Средний элемент — тот, который физически стоит посередине массива.
- Медианный элемент — элемент, значение которого находится посередине между всеми значениями в массиве
Есть ещё много других техник выбора — они применяются, когда программист точно знает, с какими массивами придётся работать: немного упорядоченными или когда всё вразнобой.
Быстрая сортировка на JavaScript
Запустите этот код в консоли браузера, чтобы посмотреть, как алгоритм шаг за шагом приводит массив в нормальный вид:
Что дальше
На этом мы закончим с обменными сортировками — впереди нас ждут интересные сортировки выбором, слиянием и даже сортировки без сравнений. Подпишитесь, чтобы не пропустить ни одной из них.
Почему быстрая сортировка на самом деле медленная? Новый метод сортировки массива
Многие программисты думают, что Quick Sort — самый быстрый алгоритм из всех существующих. Отчасти это так. Но работает она действительно хорошо только если правильно выбран опорный элемент (тогда сложность составляет ). В противном же случае асимптотика будет примерно такой же как и в пузырика (то-есть O (n 2 )).
При этом, если массив уже отсортирован, то алгоритм всё-равно будет работать не быстрее, чем за O (n log n)
Исходя из этого, я решил написать свой алгоритм для сортировки массива, который работал бы лучше за quick_sort. И если массив уже отсортирован, то не прогонять его кучу раз, как это бывает у многих алгоритмов.
Требования:
- Лучший случай
- Средний случай
- Худший случай
- В среднем быстрее быстрой сортировки
- Сортировка выбором
- Сортировка слиянием
- Сортировка вставками
А теперь давайте обо всём по порядку
Чтобы наш алгоритм всегда работал быстро, нужно чтобы в среднем случае асимптотика была хотя бы O (n log n), а в лучшем — O (n). Все мы прекрасно знаем, что в лучшем случае сортировка вставками работает за один проход. Но в худшем ей придётся гонять по массиву столько раз, сколько в нём элементов.
Предварительная информация
Начальная версия алгоритма (не оптимальная):
Основная идея алгоритма состоит в так называемом поиске максимума (и минимума). На каждой итерации выбираем из массива элемент. Если он больше предыдущего максимума, то добавляем этот элемент в конец выборки. Иначе если он меньше предыдущего минимума, то дописываем этот элемент в начало. Иначе кладём в отдельный массив.
На вход функция принимает массив и количество элементов в этом массиве
Для хранения выборки из массива (наши максимумы и минимумы) и остальных элементов выделим память
Как видим, для хранения выборки мы выделили в 2 раза больше памяти, чем наш исходный массив. Это сделано на случай если у нас массив отсортирован и каждый следующий элемент будет новым максимумом. Тогда будет занята только вторая часть массива выборки. Или же наоборот (если отсортирован по убыванию).
Для выборки сначала нужны начальные минимум и максимум. Просто выберем первый и второй элементы
Собственно сама выборка
Теперь у нас есть отсортированный набор элементов, и «остальные» элементы, которые нам ещё нужно отсортировать. Но сначала нужно произвести некоторые манипуляции с памятью.
Освобождаем неиспользуемую память
Делаем рекурсивный вызов сортировки для остальных элементов и сливаем их с выборкой
Проверим скорость работы алгоритма по сравнению с Quick Sort
Как видим, это совсем не то, чего мы хотели. Почти в 6 раз дольше, чем QuickSort! Но разы в этом контексте неуместно использовать, так как здесь значение имеет именно асимптотика. В данной реализации алгоритма в худшем случае первый и второй элементы будут минимальным и максимальным. И остальные будут скопированы в отдельный массив.
- Худший случай:
- Средний случай:
- Лучший случай:
Хм, это ничем не лучше той же самой сортировки вставками. Да, действительно мы можем найти максимальный (минимальный) элемент очень быстро, и остальные просто не попадут в выборку.
Можем попытаться оптимизировать сортировку слиянием. Для начала проверим скорость обычной сортировки слиянием:
Для простоты использования нужна какая-нибудь обёртка
Да, прирост в скорости наблюдается, но всё-же эта функция работает не так быстро, как Quick Sort. Тем более мы не можем говорить про O (n) на отсортированных массивах. Поэтому этот вариант тоже откидаем.
Варианты оптимизации первого варианта
Для того, чтобы сложность не была , мы можем складывать элементы, которые не попали в выборку не в 1 массив как ранее, а раскинуть на 2 массива. После чего останется просто отсортировать этих две подчасти, и слить их с нашей выборкой. В результате мы получим сложность равную
Как мы уже заметили, абсолютно максимальный (минимальный) элемент в сортируемом массиве может найтись довольно быстро, и это не очень эффективно. Вот тут в помощь нам вступает сортировка вставками. На каждой итерации выборки будем проверять, можем ли мы вставить поточный элемент в набор из последних, например, восьми вставленных.
Если сейчас не понятно, то не расстраивайтесь. Так и должно быть. Сейчас на коде всё станет ясно и вопросы пропадут.
Остаточный правильный вариант алгоритма:
Сигнатура такая же как и в предыдущем варианте
Но следует заметить, что данный вариант предполагает первым параметром указатель, на котором можно вызвать операцию delete[] (почему — мы увидим далее). То-есть когда мы выделяли память, мы именно для этого указателя присваивали адрес начала массива.
Предварительная подготовка
В данном примере так называемый «коэффициент навёрстывания» (catch up coefficient) — это просто константа со значением 8. Она показывает сколько максимум элементов мы попытаемся пройти, чтобы вставить новый «недо-максимум» или «недо-минимум» на своё место.
Для хранения выборки создаём массив
Если что-то непонятно, то смотрите объяснение в начальной версии
Заполним первые несколько элементов массива выборки
Напомню, что в левую сторону от центра массива выборки идут новые минимумы, а в правую — новые максимумы
Создадим массивы для хранения не избранных элементов
Теперь, самое главное — правильная выборка элементов из исходного массива
Цикл начинается с localCatchUp (потому что предыдущие элементы уже попали в нашу выборку как значения от которых мы будем отталкиваться). И проходит до конца. Так что после в конце концов все элементы распределятся либо в массив выборки либо в один из массивов недо-выборки.
Для проверки, можем ли мы вставить элемент в выборку, мы просто будем проверять больше (или равен) ли он элементу на 8 позиций левее (right − localCatchUp). Если это так, то мы просто одним проходом по этим элементам вставляем его на нужную позицию. Это было для правой стороны, то-есть для максимальных элементов. Таким же образом делаем с обратной стороны для минимальных. Если не удалось вставить его ни в одну сторону выборки значит кидаем его в один из rest-массивов.
Цикл будет выглядеть примерно так:
Опять же, что здесь происходит? Сначала пытаемся пихнуть элемент в максимумы. Не получается? — Если возможно, кидаем его в минимумы. При невозможности и это сделать — кладём его в restFirst или restSecond.
Самое сложное уже позади. Теперь после цикла у нас есть отсортированный массив с выборкой (элементы начинаются с индекса [left + 1] и оканчиваются в [right − 1]), а также массивы restFirst и restSecond длиной restFirstLen и restSecondLen соответственно.
Как и в предыдущем примере, перед рекурсивным вызовом высвобождаем память от основного массива (все его элементы мы уже и так сохранили)
У нас массив selection может содержать много ячеек неиспользуемой памяти. Перед рекурсивным вызовом нужно освободить её.
Освобождаем неиспользуемую память
Теперь запускаем нашу функцию сортировки рекурсивно для массивов restFirst и restSecond
Для понимания того как оно всё отработает, сначала нужно посмотреть код до конца. Пока что нужно просто поверить что после рекурсивных вызовов массивы restFirst и restSecond будут отсортированными.
И, наконец, нам нужно слить 3 массива в результирующий и назначить его указателю arr.
Можно было бы сначала слить restFirst + restSecond в какой-нибудь массив restFull, а потом уже производить слияние selection + restFull. Но данный алгоритм обладает таким свойством, что скорее всего массив selection будет содержать намного меньше элементов, чем любой из rest-массивов. Припустим в selection содержится 100 элементов, в restFirst — 990, а в restSecond — 1010. Тогда для создания restFull массива нужно произвести 990 + 1010 = 2000 операций копирования. После чего для слияния с selection — ещё 2000 + 100 копирований. Итого при таком подходе всего копирований будет 2000 + 2100 = 4100.
Давайте применим здесь оптимизацию. Сначала сливаем selection и restFirst в массив selection. Операций копирования: 100 + 990 = 1090. Далее сливаем массивы selection и restSecond на что потратим ещё 1090 + 1010 = 2100 копирований. Суммарно выйдет 2100 + 1090 = 3190, что почти на четверть меньше, нежели при предыдущем подходе.
Финальное слияние массивов
Как видим, если нам выгодней сливать selection с restFirst, то мы так и делаем. Иначе мы сливаем как в «restFull»
Теперь время тестирования
Небольшая ремарка: я использовал именно эту реализацию quickSort для того, чтобы всё было честно. Стандартная sort из библиотеки algorithm хотя и универсальна, но работает в 2 раза медленней представленной ниже.
Все тесты были проведены на машине на проц. Intel core i3 7100u и 8ГБ ОЗУ
Выводы
Как видим, алгоритм работает, и работает хорошо. По крайней мере всё чего мы хотели, было достигнуто. На счёт стабильности, не уверен, не проверял. Можете сами проверить. Но по-идее она должна достигаться очень легко. Просто в некоторых местах вместо знака > поставить ≥ или что-то того.