Looks like the first piece is ported from C and second - from Haskell.
2 main differences are:
Temporary lists
The first solution works in-place. It is nice because there are no temporary lists to create and then garbage collect.
This is the difference here.
Cached pivotvalue
The first solution stores pivotvalue in a temporary variable, whereas second uses L[0]
, which would generate a tiny overhead because of array access. (or maybe not if it gets cached somewhere down the road)
A little difference in how algo works stems from using/not using temporary lists. "pick elements less than pivotvalue, then pivotvalue itself, then elements greater or equal" is easy to comprehend, but requires enough memory to store a whole copy of the list. If you try to implement that in-place instead, you'll end up with what there's at first solution. This piece has O(1)
memory complexity in the first case and O(n)
in the second.
Speaking of time complexity, leaving housekeeping for temporary lists aside, both algos are similar: in each partitioning, each element gets visited once (in the first case) and twice (in the second case), no matter how big our array is.
However, maintaining temporary lists must have some overhead.
It is said that appending a list is O(1)
but also that lists sometimes grow out of allocated size and everything has to be moved then. I'm not sure yet how that works in case of many appends to an array, or if it applies to creating lists through comprehension. I'll check this moment and elaborate on it.
Upd: looks like under the hood list comprehensions do append to an array.
If we take a look at list
's source, we can see a comment that says:
This over-allocates proportional to the list size, making room for additional growth. The over-allocation is mild, but is enough to give linear-time amortized behavior over a long sequence of appends()
So, I suppose, we should assume that appending a list is O(1).
That being said, the final judge will be timeit
on actual data, but the first solution is closer to hardware and should be faster. I don't see algorithmic reasons for the second code to be faster, besides it being more high-level and eligible to some optimisations by the interpreter (dubious). The second code should also consume more memory.
Both suffer from typical qsort problems like bad performance on already sorted-ish arrays (because sub-arrays are getting partitioned like []
and sub_array[1:]
)
You were interested in time complexity and memory usage, so rant about code style goes to this separate section.
Neither of those pieces look pythonic. The second one was way easier to understand than the first one, but it has its performance problems.
The first one uses 3 lines and one temp variable to swap values, whereas it's a one-liner in Python.
Also there's naming (snake_case
is recommended). It's also not expressive enough: quickSortHelper
does something related to quickSort - that's obvious, but what exactly?
As it handles recursion it should say so on the label.
Both quickSortHelper
and partition
could be defined inside quickSort
, or in some namespace so that you won't have name collision and also won't have to prepend names with quickSort
. That better be consistent, too - so you have recursive_traverse
and partition
or quickSortHelper
and quickSortPartition
, but not one of each.
And, of course, you should probably use sorted
instead of either of those