Pseudo-quicksort time complexity
Posted
by
Ord
on Stack Overflow
See other posts from Stack Overflow
or by Ord
Published on 2012-07-06T03:58:33Z
Indexed on
2012/07/07
15:16 UTC
Read the original article
Hit count: 244
I know that quicksort has O(n log n)
average time complexity. A pseudo-quicksort (which is only a quicksort when you look at it from far enough away, with a suitably high level of abstraction) that is often used to demonstrate the conciseness of functional languages is as follows (given in Haskell):
quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]
Okay, so I know this thing has problems. The biggest problem with this is that it does not sort in place, which is normally a big advantage of quicksort. Even if that didn't matter, it would still take longer than a typical quicksort because it has to do two passes of the list when it partitions it, and it does costly append operations to splice it back together afterwards. Further, the choice of the first element as the pivot is not the best choice.
But even considering all of that, isn't the average time complexity of this quicksort the same as the standard quicksort? Namely, O(n log n)
? Because the appends and the partition still have linear time complexity, even if they are inefficient.
© Stack Overflow or respective owner