Re: [Haskell-cafe] List as input

On Wed, Oct 15, 2008 at 5:44 PM, leledumbo wrote:

module Main where

import Data.List

-- quicksort of any list qsort [] = [] qsort (x:xs) = 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)

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.