Complex time complexity

Question

I know that quicksort has an average time complexity of O(n log n) . The pseudo-quicksort (which is only a quick sort, when you look at it far enough, with a fairly high level of abstraction), which is often used to demonstrate the brevity of functional languages, looks like this (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 a problem. The biggest problem is that it doesn't sort, which is usually a big advantage of quicksort. Even if it does not matter, it will still take longer than a typical high-speed sorting, because it must do two passes of the list when it separates them, and it does expensive add operations to merge them back together. In addition, the choice of the first element as a bar is not the best choice.

But even with all this, isn't the average time complexity of this quicksort the same as the standard quicksort? Namely, O(n log n) ? Since the addition and section still have linear time complexity, even if they are inefficient.

Answer 1

This “quicksort” is actually a deforestation tree view: http://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell

 data Tree a = Leaf | Node a (Tree a) (Tree a) mkTree [] = Leaf mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs)) 

The binary tree is unbalanced, so O (N ^ 2) is the worst and O (N * Log N) is the average size of complexity for constructing the search tree.

 foldTree fg Leaf = g foldTree fg (Node xlr) = fx (foldTree fgl) (foldTree fgr) treeSort l = foldTree (\x lft rht -> lft++[x]++rht) [] (mkTree l) 

The search algorithm has the worst case O (N ^ 2) and average size complexity O (N * Log N).

Balanced:

 Prelude> let rnds = iterate step where step x = (75*x) `mod` 65537 Prelude> length . quicksort . take 4000 . rnds $ 1 4000 (0.08 secs, 10859016 bytes) Prelude> length . quicksort . take 8000 . rnds $ 1 8000 (0.12 secs, 21183208 bytes) Prelude> length . quicksort . take 16000 . rnds $ 1 16000 (0.25 secs, 42322744 bytes) 

Not so well balanced:

 Prelude> length . quicksort . map (`mod` 10) $ [1..4000] 4000 (0.62 secs, 65024528 bytes) Prelude> length . quicksort . map (`mod` 10) $ [1..8000] 8000 (2.45 secs, 241906856 bytes) Prelude> length . quicksort . map (`mod` 10) $ [1..16000] 16000 (9.52 secs, 941667704 bytes) 

Answer 2

I agree with your assumption that the average time complexity is still O(n log n) . I am not an expert and 100% sure, but these are my thoughts:

This is the quicksort pseudocode in place: (calling quicksort with l = 1 and r = array length)

 Quicksort(l,r) -------------- IF rl>=1 THEN choose pivot element x of {x_l,x_l+1,...,x_r-1,x_r} order the array-segment x_l,...x_r in such a way that all elements < x are on the left side of x // line 6 all elements > x are on the right side of x // line 7 let m be the position of x in the 'sorted' array (as said in the two lines above) Quicksort(l,m-1); Quicksort(m+1,r) FI 

Then, the average time complexity is analyzed, choosing "<" - comparisons in lines 6 and 7 as the dominant operation in this algorithm, and finally comes to the conclusion that the average time complexity is O (n log n). Since the cost of the string "orders the segment of the array x_l, ... x_r in such a way that ..." is not taken into account (only an important operation is important when analyzing the time complexity if you want to find the boundaries), I think "because it has to make two passes list when it breaks it, "this is not a problem, just as your version of Haskell will take about twice as much of this step. The same is true for the operation application, and I agree that this does not add anything to the asymptotic costs:

Since the addition and section still have linear time complexity, even if they are inefficient.

For convenience, suppose this adds “n” to our time complexity costs, so that we have “O (n log n + n)”. Since there is a positive integer o so that n log n> n for all positive integers greater than o, it is true that you can evaluate n log n + n from above by 2 n log n and from below by n log n, therefore n log n + n = O (n log n).

In addition, the choice of the first element as a bar is not the best choice.

I think that the choice of the rotation element does not matter here, because in the average case analysis you assume a uniform distribution of elements in the array. You cannot know from which place in the array you should select it, and therefore you need to consider all these cases in which your rotation element (no matter where in the list you receive it) is the ith smallest element of your list, for i = 1 ... r.

Answer 3

I can offer you an Ideone.com runtime test , which seems to show more or less linear time intervals for both (+ +) and one that uses the battery technique from Landei's answer, as well as the other, using a one-time three disk partition . According to ordered data, it becomes quadratic or worse for all of them.

 -- random: 100k 200k 400k 800k -- _O 0.35s-11MB 0.85s-29MB 1.80s-53MB 3.71s-87MB n^1.3 1.1 1.0 -- _P 0.36s-12MB 0.80s-20MB 1.66s-45MB 3.76s-67MB n^1.2 1.1 1.2 -- _A 0.31s-14MB 0.62s-20MB 1.58s-54MB 3.22s-95MB n^1.0 1.3 1.0 -- _3 0.20s- 9MB 0.41s-14MB 0.88s-24MB 1.92s-49MB n^1.0 1.1 1.1 -- ordered: 230 460 900 1800 -- _P 0.09s 0.33s 1.43s 6.89sn^1.9 2.1 2.3 -- _A 0.09s 0.33s 1.44s 6.90sn^1.9 2.1 2.3 -- _3 0.05s 0.15s 0.63s 3.14sn^1.6 2.1 2.3 quicksortO xs = go xs where go [] = [] go (x:xs) = go [y | y<-xs, y<x] ++ [x] ++ go [y | y<-xs, y>=x] quicksortP xs = go xs where go [] = [] go (x:xs) = go [y | y<-xs, y<x] ++ (x : go [y | y<-xs, y>=x]) quicksortA xs = go xs [] where go [] acc = acc go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc) quicksort3 xs = go xs [] where go (x:xs) zs = part x xs zs [] [] [] go [] zs = zs part x [] zs abc = go a ((x : b) ++ go c zs) part x (y:ys) zs abc = case compare yx of LT -> part x ys zs (y:a) bc EQ -> part x ys zs a (y:b) c GT -> part x ys zs ab (y:c) 

the empirical run-time complexity is estimated here as O(n^a) where a = log( t2/t1 ) / log( n2/n1 ) . _{The timings are very approximate, since the ideon is not very reliable, but sometimes far enough, but enough to check its complexity.}

Thus, these data show that a single-pass partition is 1.5x-2x faster than two-pass partitions, and that using (++) no way slows down the operation. That is, “add operations” are not “expensive”. Quadratic behavior or (++) / append is an urban myth. in the context of Haskell (editing: ... i.e. in the context of protected recursion / tail recursion mod cons , cf. this answer ) (updated: as user: AndrewC explains , it is very large with a left fold, linear when (++) used with the right fold, more about this here and here ).

Answer 4

I don’t know how much this improves the execution complexity, but with the help of the battery, you can avoid the expensive (++) :

 quicksort xs = go xs [] where go [] acc = acc go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc) 

Answer 5

Look at the real O (n log n) operating system, which will work with arrays and lists: http://citeseer.ist.psu.edu/viewdoc/download?doi=10.1.1.23.4398&rep=rep1&type= pdf Its pretty easy to implement in Common Lisp, and it surpasses the sorting implementation of many commercial lys.

Answer 6

Yes, this version has the same asymptotic complexity as the classical version - you replace the linear partition time with: two passes ( < and >= ), and you have additional linear time ++ (which includes linear redistribution / copying) . Thus, it is a hefty constant factor worse than the local section, but it is still linear. All other aspects of the algorithm are the same, therefore, the same analysis is performed here, which gives the average value of O (n log n) for the “true” (that is, in place) fast sorting.