5

The partition method in the question, partition(a, lo, hi) is called Hoare’s partition scheme, which is the most classic partition scheme used in quicksort. Here is the situation. There are $n$ numbers that are non-equal pairwise. Array $a=(a_0, a_1, \cdots, a_{n-1})$ is a uniformly-random permutation of those $n$ numbers. We will run the method partition(a,...


3

qsort is not Quicksort. qsort is whatever the implementor of the standard library decided. Sorting 50 million identical values is highly unrepresentative. There are qsort implementations that will sort 50 million identical, or 50 million sorted or reverse sorted elements in linear time. Radix sort of 50 million numbers with six digits is obviously nonsense....


2

A very simple proof: I claim that if there are d integers with values between x and y, and there are n ≥ 2 elements in the array, then the probability that x and y are compared is 2 / (d + 2), independent of n. Proof by induction: If n = 2 then clearly d = 0, so the claim is that x and y are compared with probability 2 / (0 + 2) = 1. This is also clearly ...


2

The idea of the proof is to compute, for any two elements $x,y$ in the array, the probability that they are compared in the algorithm. This probability could potentially depend on the entire array. However, it turns out that you can compute it only given the order statistics of $x,y$, that is, their relative order in the sorted array. If you know that $x$ is ...


2

With the help from a fellow friend I came to the following conclusion: We know that we have to make $$n-1,n-2, \dots, 2,1 \text{ comparisons}$$ So when looking at the arithmetic series $$\sum_{i=1}^n k = \Theta(n^2)$$ We can conclude that $T(n) = \Theta(n^2)$. Please comment if I can improve my answer in any way.


2

Let us replace $\Theta(n)$ with $n$, for concreteness, and assume a base case of $T(0) = 0$. Let's try to prove inductively that $T(n) \geq cf(n)$, where $f(n) = n\log n$ for all $n$ (where $0\log 0 = 0$). During the proof, we will need to minimize $f(q) + f(m-q)$ for $0 \leq q \leq m$. Since $f'(n) = \log n + 1$, any minimum point must satisfy $$ \log q + ...


1

The number of "work" being done, should be counted with the big-O notation. This means - that you count the while loop as $O(n)$ and any other constant work done (for example, the work after the while) is $O(1)$ and $O(n)+O(1)=O(n)$ so it wont make a difference. Counting the "work" without big-O is not well-defined in the general case - so you should avoid ...


1

You can use the recursion tree method. The amount of work on the level at depth $0$ is at least $c n$ for some constant $c$ (from the $\Theta(\cdot)$ notation). The amount of work at depth $1$ is at least $c q + c (n-q -1) = c(n-1)$. The amount of work on the next level is at least $c(n-3)$ and, in general, the total amount of work on the level at depth $d$ ...


1

If $p \leq k \leq i$ then $A[k] \leq x.$ In the algorithm when for example, $p$ is $1$, won't $i$ be $0$.... How would this hold, since before the for loop we have i = p-1 Although, as you have observed, $i$ is always smaller than $p$ at the start of the loop, it might become bigger because the statement "$i=i+1$" in the loop could be executed. Once $i$ ...


1

This depends... If the number of input numbers is $n$, assuming the word-ram model of computation, a word size of $\Theta(\log n)$ bits, and worst-case inputs: Radix sort would require $O(n \log n)$ time and $O(n)$ auxiliary space. Quicksort with fixed or random pivot selection would require $O(n^2)$ worst-case time and $O(\log n)$ auxiliary space. ...


1

If you either use a compiler that supports tail recursion, or make the small change not to use recursion for the larger partition at all, the recursion depth depends on the sizes of the smaller intervals. The worst case for recursion depth is the case that each partition divides your subarray exactly in half, making the depth $log_2 (n)$. The best case for ...


1

The usual rule here is only one question per post. Link [2] doesn't say that random pivot and median pivot lead to $O(n^2)$ time complexity. The median of first, middle, and last element is not the median of the whole array. Writing "median pivot" is probably a bad idea, unless you have carefully specified what that's a median of. Link [1] says that ...


1

With the substitution method, you add up $\Theta(n) + \Theta(n-1) = ... + \Theta(1)$, roughly n times $\Theta(n)$, therefore about $n^2$. Note that this is for an initial guess - to help you make a guess your maths doesn't have to be strict. To prove it, you need to be strict. If you have a sum that isn't as simple as this one here, you can just give a ...


Only top voted, non community-wiki answers of a minimum length are eligible