Здравствуйте, kochetkov.vladimir, Вы писали:

KV>Здравствуйте, PC_2, Вы писали:


PC_>>Спасибо, но это не Квик сорт. Это его пародия.
PC_>>Алгоритм Квик сорт включает перемещение элементов на "одном участке" памяти.
PC_>>Тоесть не требует дополнительных ресурсов памяти.

PC_>>Тоесть банально этот код не решает поставленную задачу. Точка.

KV>Предлагаю со столь смелым заявлением отправляться сразу сюда: http://rsdn.ru/forum/decl/, а я пока за попкорном сбегаю. Троеточие...

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

1. Может ли?
2. Если да, то как? Интересует последовательность преобразований, алгоритм работы оптимизирующего компилятора в данном конкретном случае (общие стространичные статьи по устройству оптимизатора, например, в хаскеле на данный момент не интересуют).
Хотелось бы увидеть не эвристический алгоритм.
3. Хотелось бы увидеть код на высокоуровневом языке программирования и листинг машинного или байт кода.

Разумеется требуется получить код, который выполняет быструю сортировку без использования дополнительной памяти больше чем с*lg(n).

PS На самом деле, это очень важный вопрос и его разрешение сильно помогло бы популяризации функциональных языков программирования. Уверен, многие из тех, кто интересуется функциональным программированием, но так и не начал использовать его для чего-то большего чем просто "поиграться", не делают этого именно потому, что у них не укладывается в голове, как это можно писать такие неоптимальные с точки зрения производительности (не программиста, а вычисления на компьютере ) программы.
Статьи по функциональому программированию нужно начинать не с определения натурального числа (мне всегда было, что же там получается в итоге при компиляции. кстати что?) или факториала сверткой по списку и как это круто, а с того, что некоторый код на традиционном ЯП можно кратко записать использовав ФП, а в резулятате получить тот же машинный код. И таким образом показывать, какие же реальные проблемы может решить функционально программирования, не создав новых.