то есть, coq/agda не тянешь? Не стыдно? // в чём разница, из какого языка мутировать массив?

@gds В том-то и дело, что не мутировать. Я смог вспомнить только наивный подход, создающий новые списки — sort (x:xs) = let (left, right) = Data.List.partition (< x) xs in (sort left) ++ [x] ++ (sort right) (и ещё кейс для пустого списка) Сейчас глянул на псевдокод на Rosetta Code, сразу вспомнил и старую добрую версию с индексами и мутируемым массивом. Coq/Agda что-то не пробовал даже. Считаю себя пока что не готовым к зависимым типам.

@minoru в том-то и дело, что quicksort -- алгоритм сортировки массивов.

Типичный синдром хаскеллиста. Бросай это дело пока на помойке не оказался.

@gds А как сортировать списки? Превращать в дерево (n·log n) и обратно в список (n) (в итоге n·log n, неплохо вроде)?

@anonymous Пруф или не обнаружил себя пишущим на Python за еду.

@minoru Вот-вот. А мог бы уже в гугле каком-нибудь не за еду писать если бы хуйней не страдал.

@anonymous Я пока ещё молод, наивен и верю, что лучше писать на чём-то вменяемом (я не о Python сейчас) за меньшие плюшки, чем на чём-то убогом за бо́льшие.

@minoru дерево -- грамотно. merge sort тоже вроде вписывается ок. А зачем вообще списки нужны, если встаёт вопрос об их эффективной сортировке? Есть деревья, хештаблицы.

@gds О, merge sort когда-то учил, но на практике ни разу не пригождался. Про списки — это уже новый разговор (старый, начавшийся моим постом, ты отлично закончил в /PCS). Тут можно пофантазировать; к примеру, может статься так, что у тебя вся логика красиво ложится на списки, но вот на одном из этапов нужно бы отсортировать.

@minoru вот кстати да. У меня в одной хобби-задачке логика идеально ложится на почти списки -- на потоки элементов (потоковый доступ, чанки там, хуё-моё). Там и merge sort прикидываю, и ещё всякое. Думаю бигдату нормальную захуячить ("суп из семи хадуп" не норм).

@gds В /XR0 я сказал, что этот твой коммент закончил эту ветку разговора, но вот теперь сижу и не могу понять, с чего бы это наивная имплементация (та, что продит новые массивы или списки) хуже того же merge sort или дерева. Амортизированная стоимость та же, по памяти тоже одинаково выходит… Короче, я не понял, почему это quicksort в общем случае именно для массивов предназначен.

@minoru не уверен насчёт стоимости, подумаю на досуге, интересно. Но в чём точно разница -- если плодят новые массивы или выделяют ячейки списка, то уже по памяти выходит не одинаково. Да и сами алгоритмы разные. В одном месте -- доступ по индексу, в другом -- обработка списков с головы до хвоста. Понятно, что идея общая ("разделяй и властвуй" (хотя в quicksort on lists есть ещё шаг "объединяй")). А вот анализ производительности и корректности у них будет разный. А ведь алгоритм -- это как раз то, что пригодно к анализу (а потом уже превращается в код, не важно, на каком языке).