Используется ли нерекурсивная реализация быстрой сортировки на реальных проектах?
Мой препод по проге сильно фанатеет от нерекурсивной быстрой сортировки, требует использовать только её, говорит что она прям гораздо эффективнее. Действительно ли это так, и используется ли такая реализация в настоящей работе в компаниях или классическая рекурсивная реализация все таки популярнее?
Ответы (2 шт):
Она действительно может быть эффективнее. Всё зависит от обстоятельств и от того, что вы вкладываете в это слово. Дело в том, что если машина сильно ограничена по памяти, то вызов функции рекурсивно - будет существенной нагрузкой, а значит применение нерекурсивной реализации более целесообразно. В то же время, принято считать, что рекурсия работает быстрее(то есть с точки зрения скорости работы имеет преимущество), хотя так ли это в конкретном случае - неизвестно, по крайней мере до тех пор, пока мы говорим общими словами.
Если вам это действительно интересно, вы можете провести сравнение(вот пример, или вот), промоделировав работу этих 2 алгоритмов в разных условиях, выявить особенности. Результаты оформить в виде научной статьи, отправить в какой-нибудь журнал или выступить на студенческой научной конференции, можете опубликовать на хабре и поделиться тут. Только не забудьте, что в вашем исследовании должна быть научная новизна(быть может такое исследование уже есть, ищите).
Вдобавок скажу, что академическое образование направлено на расширение кругозора прежде всего, а не на то, чтобы сделать из вас ремесленника. Образование знакомит с разными областями предметной области и учит искать подходы к решению проблемы, учит учиться, поэтому в рамках учебной деятельности ваш преподаватель правильно делает, что знакомит вас с алгоритмами с разных сторон.
Нерекурсивные варианты рекурсивных алгоритмов в реальности используются довольно редко, поскольку зачастую они сводятся просто к ручной реализации стека (то, что называется "закат солнца вручную"). Помимо увеличения сложности алгоритма на пустом месте, подобный подход требует выделить под этот ручной стек область памяти неизвестного заранее размера, а лишнее динамическое выделение памяти - это всегда плохо.
Чаще всего используют "полурекурсивные" варианты, в котором одна из веток сортируется рекурсивно, а вторая - в цикле. Условная схема:
fn sort(array, low, hi) {
while (low < hi) {
middle = partition(array, low, high);
sort(array, low, middle); // левая ветка сортируется рекурсивно
low = middle; // правая ветка сортируется без рекурсии
}
}
Также популярным "трюком" является переключение на другие алгоритмы при выполнении некоторых условий, а именно на сортировку вставками для малых массивов и на пирамидальную сортировку при превышении лимита рекурсии.
Алгоритм быстрой сортировки, использующий этот трюк, называется Introsort.
Вот результаты быстрого анализа стандартных библиотек:
- C# - используется полурекурсивный Introsort;
- Java - используется полурекурсивный Dual Pivot Quicksort (тоже с трюками);
- C++ - используется полурекурсивный Introsort;
- Python - используется вообще TimSort, относящийся к классу сортировок слиянием.
Как видно, нерекурсивная быстрая сортировка не используется. И чистая классическая тоже не используется.