От: | NikeByNike | ||
Дата: | 09.01.10 17:13 | ||
Оценка: | 1 (1) |
Пример 1. Быстрая сортировка Хоара на Си
void qsort(int *ds, int *de, int *ss){
int vl = *ds, *now = ds, *inl = ss, *ing = ss + (de - ds);
if ( de <= ds + 1 ) return;
for( ; now != de; ++now ){
if ( *now <= vl ) *inl++ = *now;
else *ing-- = *now;
}
*++inl = vl;
qsort(ds, ds + (inl - ss), ss);
qsort(ds + (inl - ss), de, inl + 1);
}
Пример 3. Быстрая сортировка Хоара на языке Haskell
quickSort [] = []
quickSort (x:xs) = quickSort [y | y <- xs, y <= x] ++ [x] ++ quickSort [y | y <- xs, y > x]
Первое что метнулось в глаза — автор сделал акцент на времени компиляции (но это ладно) и размере кода! Но размер кода бывает актуален очень редко, особенно в случае функциональных языков с их рантаймом. А вот на скорость это влияет очень плохо — но я не в первый раз вижу как пиарщики функциональных языков про это не упоминают.В языке Си++ имеется такое понятие, как шаблон, которое позволяет программисту определять полиморфные функции, подобные quickSort. В стандартную библиотеку Си++ — STL — входит такая функция и множество других полиморфных функций. Но шаблоны Си++, как и родовые функции Ады, на самом деле порождают множество перегруженных функций, которые, кстати, нужно каждый раз компилировать, что неблагоприятно сказывается на времени компиляции и размере кода. А в функциональных языках полиморфная функция quickSort — это одна единственная функция.