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