Haskellのウェブサイトでは、非常に魅力的な5行のクイックソート機能下記の通りです。
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
where
lesser = filter (< p) xs
greater = filter (>= p) xs
また、「C での真のクイックソート」。
// To sort array a[] of size n: qsort(a,0,n-1)
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);
a[hi] = a[l];
a[l] = p;
qsort( a, lo, l-1 );
qsort( a, l+1, hi );
}
}
Cバージョンの下のリンクは、「はじめにで引用したクイックソートは「本物の」クイックソートではなく、C コードのように長いリストに対応しません。」
上記の Haskell 関数が真のクイックソートではないのはなぜですか? 長いリストではスケーリングできないのはなぜですか?
ベストアンサー1
真のクイックソートには 2 つの優れた点があります。
- 分割して解決する: 問題を 2 つの小さな問題に分割します。
- 要素をその場で分割します。
短い Haskell の例では (1) を示していますが、(2) は示していません。(2) の実行方法は、そのテクニックをまだ知らないと明らかではないかもしれません。