qsort [] = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)
Коротко, красиво, и главное сразу видно что она сработает.
Вот реализация (одна из) функции quicksort на языке С:
void qsort(int a[], int lo, int hi) {
{
int h, l, p, t;
if (lo < hi) {
l = lo;
h = hi;
p = a[hi];
do {
while ((l < h) && (a[l] <= p))
l = l+1;
while ((h > l) && (a[h] >= p))
h = h-1;
if (l < h) {
t = a[l];
a[l] = a[h];
a[h] = t;
}
} while (l < h);
t = a[l];
a[l] = a[hi];
a[hi] = t;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
Длинно, непонятно, и только для массива целых чисел, для других типов придется писать свою или обобщать эту. Кстати, вот императивная реализация того же на Haskell. Еще более некрасиво...
Очевидно что на Haskell получилось лучше, правда? Не совсем...
По коду на С видно (ок, мне видно) что дополнительной памяти в процессе сортировки не выделяется хотя стек растет. Впрочем этого(роста стека) можно было бы и избежать (частично).
Можно ли сказать это про реализацию на Haskell?
Далее...как ни странно но реализаций алгоритма quicksort может быть больше одной... Например реализуя руками этот алгоритм я привык брать в качестве "опорного" элемента элемент из серидины массива. Ну да это мелочь...А вот что более существенно:
Неправильный qsort() в Solaris
Выжимка - оказывается, quicksort() в Solaris работает очень медленно, если в сортируемом массиве много одинаковых подряд идущих значений.
Вот по ссылке для других OS (смотреть только на общую "тенденцию", эксперемент был не на скорость).
| Операционная система | хорошая | плохая | разница |
| FreeBSD 4.3 | 1.6 | 1.2 | 0.8 |
| Linux RedHat 6.2 | 3.5 | 3.0 | 0.9 |
| Windows NT 4.0 SP5 | 2 | 12 | 6.0 |
| Solaris 7, x86 | 3.0 | 65.0 | 22.0 |
| Solaris 8, x86 | 2.6 | 62.0 | 24.0 |
В обоих случаях на Solaris "плохая" программа выполняется существенно медленнее.
Оказывается, из-за этого под Solaris'ом очень медленно работают запросы PostgreSQL с сортировкой.
Кстати на NT та же проблема. Как сейчас не знаю, не проверял.
Выводы - иногда на алгоритмы накладываются дополнительные требования (основное - чтобы алгоритм работал). Как правило это требования по скорости, по памяти, по использованию каких-либо других ресурсов, по сложности. Используя С для реализации алгоритма quicksort я на эти вопросы ответить могу. Используя Haskell - нет.