I run the below quick sort Haskell function (using merge and sort algorithm):
qsort []=[]
qsort (x:xs) =
qsort smaller ++ [x] ++ qsort larger
where
smaller = [a | a <- xs , a<x ] -- edit
larger = [b | b <- xs , b>=x ]
In order to test the runtime for this for a bit big amount of data, I run the below code:
qsort [100000,99999..0]
It takes till now 40 min and it is still running! Even a list of 100,000 is not that big, so:
The worst case time of quicksort is n2. Your implementation uses the first element as the pivot, which results in worst-case performance when the input is sorted (or sorted in reverse).
To get quicksort to perform at its expected complexity of n log n, you need either randomized pivot selection, or to randomly shuffle the input before sorting.
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加