[Haskell-cafe] List as input

[Toby Hutton]

On Wed, Oct 15, 2008 at 5:44 PM, leledumbo <leledumbo_cool at yahoo.co.id> wrote:
>
> module Main where
>
> import Data.List
>
> -- quicksort of any list
> qsort []     = []
> qsort (x:xs) = qsort(filter(<x) xs) ++ [x] ++ qsort(filter(>=x) xs)
>
> -- optimized quicksort, uses middle element as pivot
> qsortOpt [] = []
> qsortOpt x  = qsortOpt less ++ [pivot] ++ qsortOpt greater
>  where
>    pivot = x !! ((length x) `div` 2)
>    less = filter (<pivot) (delete pivot x)
>    greater = filter (>=pivot) (delete pivot x)
>
> main = do
>  putStr "Enter a list: "
>  l <- readLn
>  print (qsortOpt l)
> -- end of code

I'm curious as to why taking the pivot from the middle is an
'optimized' version.  For this to be true you must be making some
assumptions about the contents of the list.