Quicksort in scala

Basic Algorithm

Step 1: Choose pivot p as some element in the array.
Step 2: Partition the array so that everything on the left of p is < p and everything on the right > p (this step is $O(n)$).
Step 3: Recurse on the left and right.

Best and worse cases

Intuitively the best case is when the pivot happens to be the median each time. $O(n * log(n))$

The worst case would be choosing pivot = first element where the array is already sorted. $O(n^2)$

Implementation

There are two main implementation to consider. The first is the most intuitive:


Analysis of Lomuto quicksort

We can see that the partition method is $O(n) = a*n + c_1$

The check 'if (r < l)' occurs in constant time, $c_2$

The go method is more interesting. We can say that in the best case, when the partition is at the median every time

$$T(n) = 2 T (\frac{n}{2}) + (a * n + c_1) + c_2 = 2 T (\frac{n}{2}) + a * n + c_3  $$

Constant doesn't really make much difference as $n \rightarrow \infty $ so let's drop it:

$$T(n) = 2 T (\frac{n}{2}) + a * n  $$

$$T(\frac{n}{2}) = 2 T (\frac{n}{4}) + \frac{a * n}{2} $$
$$ => T(n) = 2 \{ 2 T (\frac{n}{4}) + \frac{a * n}{2} \} + a * n $$
$$ => T(n) = 4 T (\frac{n}{4}) + 2 * a * n $$
$$ => T(n) = 2^k * T(\frac{n}{2^k}) + k * a * n $$

We want to find this formula in terms of $T(1)$

$$ 1 = \frac{n}{2^k}$$

$$ => 2^k = n $$

$$ => k = log_2(n) $$

Substitute this value of $k$ into the earlier formula:

$$ => T(n) = 2^{log_2(n)} * T(1) + log_2(n) * a * n $$

$$ => T(n) = n * T(1) + a * n * log_2(n)  $$

$T(1)$ will happen in constant time $c$

$$ => T(n) = n * c + a * n * log_2(n)  $$

So we can see that the time complexity should be $n * log_2(n)$

Hoare Partitioning

The other implementation of quicksort is less intuitive. Apparently it does fewer swaps (x3 fewer) than lomuto, but the analysis is too complicated for me to bother with right now.

def hoare(): Unit = {
  def swap(i: Int, j:Int) = { val t = a(i); a(i) = a(j); a(j) = t }

  def aux(l: Int, r: Int): Unit = {
    val p = a(l + r / 2)
    var i = l
    var j = r

    while (i < j) {
      while (a(i) < p) i += 1            while (a(j) > p) j -= 1
      if (i <= j) { swap(i,j); i+= 1; j -= 1 }

      if (l < j) aux(l, j)
      if (r > i) aux(i,r)

    }
  }
  aux(0, a.length-1)
}