Quicksort

Practice problem: LeetCode 912. Sort an Array
Tony Hoare interview on inventing Quicksort

Hoare partition method

Explanation and visualization

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        std::srand(static_cast<unsigned>(std::time(nullptr)));
        qs(nums, 0, nums.size() - 1);
        return nums;
    }

    void qs(vector<int>& values, int left, int right) {
        int p = values[left + r(right - left)];

        int i = left;
        int j = right;

        while (i <= j) {
            while (i <= j && values[i] < p) ++i;
            while (i <= j && values[j] > p) --j;

            if (i <= j) {
                std::swap(values[i], values[j]);
                ++i;
                --j;
            }
        }

        if (left < j) qs(values, left, j);
        if (i < right) qs(values, i, right);
    }

    int r(int max) {
        if (max > 0) {
            return std::rand() % max;
        }
        return 0;
    }
};

function sortArray(nums: number[]): number[] {
  qs(nums, 0, nums.length - 1)
  return nums
}

function qs(values: number[], left: number, right: number) {
  const pivot = values[Math.floor(left + Math.random() * (right - left))]

  let i = left
  let j = right

  while (i <= j) {
    while (i <= j && values[i] < pivot) ++i
    while (i <= j && values[j] > pivot) --j

    if (i <= j) {
      const temp = values[i]
      values[i] = values[j]
      values[j] = temp
      ++i
      --j
    }
  }

  if (left < j) qs(values, left, j)
  if (i < right) qs(values, i, right)
}

It's known that the election of the pivot element will affect the performance of the algorithm. In the implementation above, the pivot is chosen randomly. This is a simple and effective way to avoid the worst-case scenario. The worst-case scenario occurs when the pivot is the smallest or largest element in the partition. In this case, the partitioning step will not divide the array into two parts of equal size. The time complexity of the algorithm will be O(n^2) instead of O(n log n).

Lomuto partition method

This partition method is commonly used online. I had always used the Hoare partition method and found this one when refreshing my memory on quicksort.

Lomuto's popularity is due to its simplicity and ease of implementation but I immediately noticed that it it was likely to be less efficient than Hoare's method. I was right. Lomuto's method is less efficient than Hoare's method because it does more swaps. The number of swaps is proportional to the number of elements that are equal to the pivot. In the worst case, when all elements are equal to the pivot, the number of swaps is proportional to the square of the number of elements. This is why Lomuto's method is not used in practice.

In the problem above the Hoare partition method runs in 85ms while Lomuto runs in 2262ms (26x slower).

Explanation and visualization

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        std::srand(static_cast<unsigned>(std::time(nullptr)));
        qs(nums, 0, nums.size() - 1);
        return nums;
    }

    void qs(vector<int>& values, int left, int right) {
        int p = left + r(right - left);

        std::swap(values[p], values[right]);

        int i = left - 1;

        for (int j = left; j < right; ++j) {
            if (values[j] < values[right]) {
                ++i;
                std::swap(values[i], values[j]);
            }
        }

        std::swap(values[i + 1], values[right]);

        if (left < i)
            qs(values, left, i);
        if (i + 2 < right)
            qs(values, i + 2, right);
    }

    int r(int max) {
        if (max > 0) {
            return std::rand() % max;
        }
        return 0;
    }
};

My Pascal implementation from 2007

Fun fact: While learning how to code, 16-year-old me used SCV (from StartCraft) as the name of the initialization function.

var fe,fs:text;
    i,tot:longint;
    l:array[1..10000] of longint;

procedure scv;
begin
  assign(fe,'d.in'); reset(fe);
  assign(fs,'d.out'); rewrite(fs);
  while not eoln(fe) do
  begin
    inc(tot);
    read(fe,l[tot]);
  end;
  close(fe);
end;

procedure qsort(desde,hasta:longint);
var j,t,m:longint;
begin
  i:=desde; j:=hasta;
  m:=l[(desde+hasta) div 2];
  repeat
    while l[i]<m do inc(i);
    while l[j]>m do dec(j);
    if i<=j then
	  begin
	    t:=l[i];
	    l[i]:=l[j];
	    l[j]:=t;
	    inc(i); dec(j);
	  end;
  until i>j;
  if desde<j then qsort(desde,j);
  if hasta>i then qsort(i,hasta);
end;

procedure temp;
begin
  for i:=1 to tot do
    write(fs,l[i],' ');
  close(fs);
end;

begin
 scv;
 qsort(1,tot);
 temp;
end.