Appendix B — Quicksort

Partitioning an Array

\begin{algorithm} \caption{PARTITION} \begin{algorithmic} \Procedure{Partition}{$A, p, r$} \State{$x=A[r]$}\Comment{The pivot} \State{$i=p-1$}\Comment{Highest index into the low side} \For{$j=p$ to $r-1$}\Comment{Process each element other than the pivot} \If{$A[j]\leq x$}\Comment{Does this element belong on the low side?} \State{$i = i+1$}\Comment{Index of a new slot in the low side} \State{exchange $A[i]$ and $A[j]$}\Comment{Put this element there} \EndIf \EndFor \State{exchange $A[i+1]$ and $A[r]$}\Comment{Pivot goes just to the right of the low side} \Return{$i+1$} \EndProcedure \end{algorithmic} \end{algorithm}

Demo

viewof n4 = Inputs.range([5, 15], {
  value: 10,
  step: 1,
  label: tex`n`
});
mutable i4 = -1;
mutable j4 = 0;
mutable q4 = n4-1;
E = d3.range(n4).map((d) => d3.randomInt(-50, 50)());

{
  increment_j; increment_i; move_pivot;
  const container = d3
    .create("div")
    .attr("width", width)
    .style("min-height", '100px')
    .style("margin-top", '30px')
    .style("margin-bottom", '30px')
  
  container
    .selectAll(".element")
    .data(E)
    .join("div")
    .attr("class", "element")
    .style("border", "3px solid lightgray")
    .style("border-style", (d, id) => id < j4 || id == n4 - 1 ? "solid" : "dashed")
    .style("background-color", (d, id) => id == q4 ? "lightgreen" : id <= i4 ? "#D2B48C" : id < j4 ? "lightblue" : id == j4 && q4 != n4 - 1 ? 'lightblue' : '' )
    .style("width", "50px")
    .style("height", "50px")
    .style("padding", "2px")
    .style("text-align", "center")
    .style("display", "inline-block")
    .style("font-size", "20px")
    .style("line-height", "40px")
    .text((d, id ) => d )
    .append("div")
      .style("position", "absolute")
      .text((d, id) => {
            let text = [];
            if(id == 0) text.push('p');
            if(id == i4) text.push('i');
            if(id == n4-1) text.push('r');
            if(id == j4) text.push('j');
            if(id == q4) text.push('q');
            return text.join(', ');
    });
  return container.node();
}

viewof increment_j = Inputs.button('increment j', {
  value: null,
  disabled: E[j4] <= E[n4-1] || j4 == n4 - 1 || q4 != n4 - 1,
  reduce: () => {
    mutable j4 += 1;
  }
});
viewof increment_i = Inputs.button('increment i', {
  value: null,
  disabled: E[j4] > E[n4-1] || j4 == n4 - 1,
  reduce: () => {
      let temp = E[i4+1];
        E[i4+1] = E[j4];
        E[j4] = temp;
        mutable i4 = mutable i4 + 1;
        mutable j4 = mutable j4 + 1;
    }
});
viewof move_pivot = Inputs.button('move pivot', {
  value: null,
  disabled: j4 < n4 - 1,
  reduce: () => {
      let temp = E[n4-1];
        E[n4-1] = E[i4+1];
        E[i4+1] = temp;
        mutable q4 = mutable i4 + 1;
    }
});

Quicksort Algorithm

\begin{algorithm} \caption{QuickSort} \begin{algorithmic} \Procedure{QuickSort}{$A, p, r$} \If{$p\leq r$} \State{} \Comment{Partition the subarray around the pivot, which ends up in $A[q]$} \State{$q=$\Call{Partition}{$A, p, r$}} \State{\Call{QuickSort}{$A, p, q - 1$}} \Comment{Recursively sort the low side} \State{\Call{QuickSort}{$A, q + 1, r$}} \Comment{Recursively sort the high side} \EndIf \EndProcedure \end{algorithmic} \end{algorithm}