Neden minimalist, örnek Haskell quicksort değil "true" quicksort?

SORU

10 EKİM 2011, PAZARTESİ

Neden minimalist, örnek Haskell quicksort değil "true" quicksort?

Haskell internet sitesi aşağıda görüldüğü gibi oldukça cazip 5 satırı quicksort fonksiyonu tanıttı.

quicksort [] = []
quicksort (p:xs) = (quicksort lesser)    [p]    (quicksort greater)
    where
        lesser = filter (< p) xs
        greater = filter (>= p) xs

Onlar da vardır"C quicksort" . doğru .

// 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 sürüm aşağıda bir link bildiren bir sayfaya yönlendirir"Quicksort Giriş alıntı "" ve c kodu gibi uzun listeler ölçek için değil quicksort.' gerçek değil

Yukarıdaki Haskell işlevi doğru bir quicksort değil mi? Ne kadar uzun listeler için ölçek için başarısız mı?

EDİT: İşte bu quicksort tanımı bulunabilir bağlantıyı. http://www.haskell.org/haskellwiki/Introduction#Quicksort_in_Haskell

CEVAP

20 EKİM 2011, PERŞEMBE

Haskell içinde quicksort: gerçek yerinde

import qualified Data.Vector.Generic as V 
import qualified Data.Vector.Generic.Mutable as M 

qsort :: (V.Vector v a, Ord a) => v a -> v a
qsort = V.modify go where
    go xs | M.length xs < 2 = return ()
          | otherwise = do
            p <- M.read xs (M.length xs `div` 2)
            j <- M.unstablePartition (< p) xs
            let (l, pr) = M.splitAt j xs 
            k <- M.unstablePartition (== p) pr
            go l; go $ M.drop k pr

Bunu Paylaş: