chapterSort.tex

\chapter{Sort}


\section{Introduction}
List of general algorithms:
\begin{enumerate}
\item Selection sort: invariant
\begin{enumerate}
\item Elements to the left of $i$ (including $i$) are fixed and in ascending order (fixed and sorted).
\item No element to the right of $i$ is smaller than any entry to the left of $i$ ($A[i]  \leq\min(A[i+1:n])$.
\end{enumerate}
\item Insertion sort: invariant
\begin{enumerate}
\item Elements to the left of $i$ (including $i$) are in ascending order (sorted).
\item Elements to the right of $i$ have not yet been seen.
\end{enumerate}
\item Shell sort: h-sort using insertion sort.
\item Quick sort: invariant
\begin{enumerate}
\item $|A_p|..\leq..|..unseen..|..\geq..|$ maintain the 3 subarrays.
\end{enumerate}
\item Heap sort: compared to quick sort it is guaranteed $O(n \lg n)$, compared to merge sort it is $O(1)$ extra space. 
\end{enumerate}

\section{Algorithms}
\subsection{Quick Sort}
\rih{Concise}. Concise but space inefficient: 
\begin{python}
def quicksort(self, A):
    if len(A) <= 1:
        return A
    pivot = A[len(A) // 2]
    left = [e for e in A if e < pivot]
    middle = [e for e in A if e == pivot]
    right = [e for e in A if e > pivot]
    return quicksort(left) + middle + quicksort(right)
\end{python}
\rih{Pivoting}. Pivoting/Partitioning to be space efficient:
\begin{python}
def quicksort(self, A, lo, hi):
    if lo >= hi:
        return
    p = pivot(A, lo, hi)
    quicksort(A, lo, p-1)
    quicksort(A, p+1, hi)
\end{python}

\subsubsection{Normal pivoting}\label{section:pivot}
The key part of quick sort is pivoting. Using the last element as pivot:
\begin{python}
def pivot(self, A, lo, hi):
    """
    pivoting algorithm:
    | left array | right array | p |
    | left array | p | right array |
    """
    p = hi
    l = lo
    for i in range(lo, hi - 1):
        if A[i] < A[p]:
            A[i], A[l] = A[l], A[i]
            l += 1
            
    A[l], A[hi] = A[hi], A[l]
    return l
\end{python}

Alternatively, Using the first element as pivot:
\begin{python}
def pivot(self, A, lo, hi):
    """
    pivoting algorithm:
    | p | left array | right array |
    | left array | p | right array |
    """
    p = lo
    l = lo  # left array ending index
    for i in range(lo + 1, hi):
        if A[i] < A[p]:
            l += 1
            A[i], A[l] = A[l], A[i]

    A[l], A[p] = A[p], A[l]
    return l
\end{python}

Notice that this implementation goes $O(N^2)$ for arrays with all duplicates.

\textbf{Problem with duplicate keys}: it is important to stop scan at duplicate
keys (counter-intuitive); otherwise quick sort will goes $O(N^2)$ for the
array with all duplicate items, because the algorithm will put all items
equal to the $A[p]$ on \textbf{a single side}. 

Example: quadratic time to sort random arrays of 0s and 1s.

\subsubsection{Stop-at-equal pivoting}
Alternative pivoting implementation with optimization for duplicated keys:
\begin{python}
def pivot_optimized(self, A, lo, hi):
    """
    Fix the pivot as the 1st element
    Scan from left to right and right to left simultaneously
    Avoid the case that the algo goes O(N^2) with duplicated keys
    """
    p = lo
    i = lo
    j = hi
    while True:
        while True:
            i += 1
            if i >= hi or A[i] >= A[lo]:
                break
        while True:
            j -= 1
            if j < lo or A[j] <= A[lo]:
                break

        if i >= j:
            break

        A[i], A[j] = A[j], A[i]

    A[lo], A[j] = A[j], A[lo]
    return j

\end{python}
\subsubsection{3-way pivoting}
This problem is also known as \textit{Dutch national flag problem}.

3-way pivoting: pivot the array into 3 subarrays: 

$$|..\leq..|..=..|..unseen..|..\geq..|$$
\begin{python}
def pivot_3way(self, A, lo, hi):
    # pointing to end of left array LT
    left = lo-1
    # pointing to the end of array right GT (reversed)
    right = hi

    pivot = A[lo]
    i = lo  # scanning pointer
    while i < right:  # not n nor hi
        if A[i] < pivot:
            left += 1
            A[left], A[i] = A[i], A[left]
            i += 1
        elif A[i] == pivot:
            i += 1
        else:
            right -= 1
            A[right], A[i] = A[i], A[right]
            # i stays

    return left, right
\end{python}
\subsection{Merge Sort}
\begin{figure}[!htp]
\centering
\subfloat{\includegraphics[width=\linewidth]{msort}}
\caption{Merge Sort}
\label{fig:msort}
\end{figure}
\runinhead{Normal merge} Normal merge sort with extra space
\begin{python}
def merge_sort(self, A):
  if len(A) <= 1:
    return

  mid = len(A) // 2
  L, R = A[:mid], A[mid:]
  self.merge_sort(L)
  self.merge_sort(R)

  l, r, i = 0, 0, 0
  while l < len(L) and r < len(R):
    if L[l] < R[r]:
      A[i] = L[l]
      l += 1
    else:
      A[i] = R[r]
      r += 1
    i += 1

  if l < len(L):
    A[i:] = L[l:]
  if r < len(R):
    A[i:] = R[r:]
\end{python}

\runinhead{Merge backward.} Merge two arrays in the place of one of the arrays.  
\begin{python}
def merge(self, A, m, B, n):
  """
  Arrays in asc order.
  Assume A has enough space.
  CONSTANT SPACE: starting backward. 
  """
  i = m-1
  j = n-1
  closed = m+n

  while i >= 0 and j >= 0:
    closed -= 1
    if A[i] > B[j]:
      A[closed] = A[i]
      i -= 1
    else:
      A[closed] = B[j]
      j -= 1

  # either-or
  # dangling
  if j >= 0: A[:closed] = B[:j+1]
  # if i >= 0: A[:closed] = A[:i+1]
\end{python}
\runinhead{In-place \& Iterative merge.}
In-place merge sort of array without recursive. The basic idea is to avoid the recursive call while using iterative solution.

The algorithm first merge chunk of length of 2, 4, 8 ... until $2^k$ where $2^k$ is large than the length of the array.
\begin{python}
def merge_sort(self, A):
  n = len(A)
  l = 1
  while l <= n:
    for i in range(0, n, l*2):
      lo, hi = i, min(n, i+2*l)
      mid = i + l
      p, q = lo, mid
      while p < mid and q < hi:
        if A[p] < A[q]:
          p += 1
        else:
          tmp = A[q]
          A[p+1:q+1] = A[p:q]
          A[p] = tmp
          p, mid, q = p+1, mid+1, q+1

    l *= 2

  return A
\end{python}
The time complexity may be degenerated to $O(n^2)$. 
\subsection{Do something while merging}
During the merging, the left half and the right half are both sorted; therefore, we can carry out operations like:
\begin{enumerate}
\item inversion count 
\item range sum count 
\end{enumerate}

\runinhead{Count of Range Sum.} Given an integer array nums, return the number of range sums that lie in $[lower, upper]$ inclusively. Make an array $A$ of sums, where \pyinline{A[i]} is \pyinline{sum(nums[:i])}; and then feed to merge sort. Since both the left half and the right half are sorted, we can diff $A$ in $O(n)$ time to find range sum. 

\begin{python}
def msort(A, lo, hi):
  if lo + 1 >= hi:
    return 0

  mid = (lo + hi)//2
  cnt = msort(A, lo, mid) + msort(A, mid, hi)

  temp = []
  i = j = r = mid
  for l in range(lo, mid):
    # range count
    while i < hi and A[i] - A[l] <  LOWER: i += 1
    while j < hi and A[j] - A[l] <= UPPER: j += 1
    cnt += j - i

    # normal merge 
    while r < hi and A[r] < A[l]:
      temp.append(A[r])
      r += 1

    temp.append(A[l])

  while r < hi:  # dangling right
    temp.append(A[r])
    r += 1

  A[lo:hi] = temp
  return cnt
\end{python}

Here, the implementation of merge sort use: 1 for-loop for the left half and 2 while-loop for the right half.

\section{Properties}
\subsection{Stability}
Definition: a stable sort preserves the \textbf{relative order of items with equal keys} (scenario: sorted by time then sorted by location). 

Algorithms:
\begin{enumerate}
\item Stable
\begin{enumerate}
\item Merge sort
\item Insertion sort
\end{enumerate} 
\item Unstable
\begin{enumerate}
\item Selection sort
\item Shell sort
\item Quick sort
\item Heap sort
\end{enumerate}
\end{enumerate}
\textbf{Long-distance swap} operation is the key to find the unstable case during sorting. 
\begin{figure}[hbtp]
\centering
\subfloat{\includegraphics[width=\linewidth]{stable_sort}}
\caption{Stale sort vs. unstable sort}
\label{fig:trie} 
\end{figure}

\subsection{Sorting Applications}
\begin{enumerate}
\item Sort
\item Partial quick sort (selection), k-th largest elements 
\item Binary search
\item Find duplicates 
\item Graham scan
\item Data compression
\end{enumerate}

\subsection{Considerations}
\begin{enumerate}
\item Stable?
\item Distinct keys?
\item Need guaranteed performance?
\item Linked list or arrays?
\item Caching system? (reference to neighboring cells in the array? 
\item Usually randomly ordered array?
(or partially sorted?)\item Parallel?
\item Deterministic?
\item Multiple key types?
\end{enumerate}

$O(N\lg N)$ is the lower bound of comparison-based sorting; but for other
contexts, we may not need $O(N \lg N)$:
\begin{enumerate}
\item Partially-ordered arrays: insertion sort to achieve $O(N)$. \textbf{Number of inversions}: 1 inversion $=$ 1 pair of keys that are out
of order.
\item Duplicate keys
\item Digital properties of keys: radix sort to achieve $O(N)$.
\end{enumerate}

\subsection{Sorting Summary}
See Figure \ref{fig:sortSummary}.
\begin{figure*}[h]
\centering
\subfloat{\includegraphics[width=0.8\linewidth]{sort_summary}}
\caption{Sort summary}
\label{fig:sortSummary} 
\end{figure*}

\section{Partial Quicksort}
\subsection{Find $k$ smallest}
\runinhead{Heap-based solution.} $O(n \log k)$

Version 1, construct heap with $n$ numbers, and take $k$: $O(n+k\log n)$, where $O(n)$ is for constructing heap. 

Version 2. construct heap with $k$ numbers, and iterate $n$: $O(k+n\log k)$. 

The 2nd version is much master than 1st based on emperical analysis; additionally, it has smaller memory impact. 

In python there are:
\begin{python}
heapq.nlargest(n, iterable[, key])
heapq.nsmallest(n, iterable[, key])
\end{python}


\runinhead{Partial Quicksort}  Then the $A[:k]$ is sorted $k$ smallest. The algorithm recursively sort the $A[lo:hi]$

The average time complexity is
\begin{eqnarray*}
F(n) = \left\{ \begin{array}{rl}
  F(\frac{n}{2})+O(n) &\mbox{// if $\frac{n}{2} \geq k$} \\
  2F(\frac{n}{2})+O(n) &\mbox{// otherwise}
       \end{array} \right.
\end{eqnarray*}
Therefore, the complexity is $O(n+k \log k)$.
\begin{python}
def partial_qsort(self, A, lo, hi, k):
    if lo >= hi:
      return

    p = self.pivot(A, lo, hi)
    self.partial_qsort(A, lo, p, k)
    if k <= p+1:
      return
    self.partial_qsort(A, p+1, hi, k)
\end{python}
The partial quick sort will find the $k$ smallest number in sorted order. If the top $k$ elements are not required to be sorted, then use find $k$-th algorithm 

\subsection{Find $k$-th: Quick Select}
Use partial quick sort to find $k$-th smallest element in the unsorted array. The algorithm recursively sort the $A[lo:hi]$

The average time complexity is
\begin{align*}
F(n) &= F(n/2) + O(n) \\
&= O(n)
\end{align*}
Refresh the \pyinline{def pivot}:
\begin{python}
def pivot(self, A, lo, hi):
    p = hi
    l = lo
    for i in range(lo, hi - 1):
        if A[i] < A[p]:
            A[i], A[l] = A[l], A[i]
            l += 1
            
    A[l], A[hi] = A[hi], A[l]
    return l  # return the pivot index
\end{python}
Find $k$-th with 2-way partitioning. Notice that only index changing while $k$ is the same.
\begin{python}
def find_kth(self, A, lo, hi, k):
    if lo >= hi:
      return
    
    p = self.pivot(A, lo, hi)
    if k == p:
      return p
    elif k < p:
      return self.find_kth(A, lo, p, k)
    else:
      return self.find_kth(A, p+1, hi, k)
\end{python}
Find $k$-th with 3-way partitioning. Pay attention to the indexing. $lt$, $gt$ means the last index of less-than portion and larger-than partion. 
\begin{python}
def find_kth(self, A, lo, hi, k):
    if lo >= hi:
      return

    lt, gt = self.pivot(A, lo, hi)
    if lt < k < gt:
      return k
    elif k <= lt:
      return self.find_kth(A, lo, lt+1, k)
    else:
      return self.find_kth(A, gt, hi, k)
\end{python}

Pivoting see section - \ref{section:pivot}.

\runinhead{Find $k$-th in union of two sorted array.} Given sorted two arrays $A, B$, find the $k$-th element (0 based index).

Core clues:
\begin{enumerate}
\item To reduce the complexity of $O(\log (m+n))$, need to half the arrays.
\item Decide which half of the array to disregard. 
\item Decide whether to disregard the median (i.e. boundary point).
\end{enumerate}
\begin{python}
def find_kth(self, A, B, k):
  if not A:  return B[k]
  if not B:  return A[k]
  if k == 0: return min(A[0], B[0])

  m, n = len(A), len(B)
  if A[m/2] >= B[n/2]:
    if k > m/2 + n/2:
      return self.find_kth(A, B[n/2+1:], k-n/2-1)  # exclude median
    else:
      return self.find_kth(A[:m/2], B, k)  # exclude median
  else:
    return self.find_kth(B, A, k)  # swap
\end{python}
\subsection{Applications}
\runinhead{Wiggle Sort.} Given an unsorted array $A$, reorder it such that $A_0 < A_1 > A_2 < A_3$. Do it in $O(n)$ time and $O(1)$ space. 

Core clues:
\begin{enumerate}
\item Quick selection for finding median (Average $O(n)$)
\item Three-way partitioning to split the data
\item Re-mapping the index to do in-place partitioning
\end{enumerate}

\runinhead{Pre-processing} Sorting can be an important pre-processing step as to:
\begin{enumerate}
\item Satisfying the output order (e.g. if multiple results are possible, output the one that's smallest in terms of the natural order). 
\end{enumerate}

\begin{python}
class Solution:
  def wiggleSort(self, A):
    n = len(A)
    median_idx = self.find_kth(A, 0, n, n/2)
    v = A[median_idx]
    
    idx = lambda i: (2*i+1)%(n|1)
    lt = -1
    hi = n
    i = 0
    while i < hi:
      if A[idx(i)] > v:
        lt += 1
        A[idx(lt)], A[idx(i)] = A[idx(i)], A[idx(lt)]
        i += 1
      elif A[idx(i)] == v:
        i += 1
      else:
        hi -= 1
        A[idx(hi)], A[idx(i)] = A[idx(i)], A[idx(hi)]

  def pivot(self, A, lo, hi, pidx=None):
    lt = lo-1
    gt = hi
    if not pidx: pidx = lo

    v = A[pidx]
    i = lo
    while i < gt:
      if A[i] < v:
        lt += 1
        A[lt], A[i] = A[i], A[lt]
        i += 1
      elif A[i] == v:
        i += 1
      else:
        gt -= 1
        A[gt], A[i] = A[i], A[gt]

    return lt, gt

  def find_kth(self, A, lo, hi, k):
    if lo >= hi: return

    lt, gt = self.pivot(A, lo, hi)
    
    if lt < k < gt:
      return k
    if k <= lt:
      return self.find_kth(A, lo, lt+1, k)
    else:
      return self.find_kth(A, gt, hi, k)
\end{python}

\section{Inversion}
If $a_i > a_j$ but $i<j$, then this is considered as 1 Inversion. That is, for an element, the count of other elements that are \textit{larger} than the element but appear \textit{before} it. This is the default definition. 

There is also an alternative definition: for an element, the count of other elements that are \textit{samller} than the element but appear \textit{after} it. 

\subsection{MergeSort \& Inversion Pair}
MergeSort to calculate the reverse-ordered paris. The only difference from a normal
merge sort is that - when pushing the 2nd half of the array to the place, you calculate
the inversion generated by the element $A_2[i_2]$ compared to $A_1[i_1:]$.

Therefore the Merge-and-count key is \pyinline{ret += len(A1) - i1}

\begin{figure}[hbtp]
\centering
\subfloat{\includegraphics[width=\linewidth]{mergeAndSort.png}}
\caption{Merge and Count}
\label{fig:mergeAndSort}
\end{figure}

\begin{python}
def merge(A1, A2, A):
  i1 = i2 =0
  ret = 0
  for i in range(len(A)):
    if i1 == len(A1):
      A[i] = A2[i2]
      i2 += 1
    elif i2 == len(A2):
      A[i] = A1[i1]
      i1 += 1
    else:
      # use array diagram to illustrate
      if A1[i1] > A2[i2]:  # push the A2 to A
        A[i] = A2[i2]
        i2 += 1
        # number of reverse-ordered pairs
        ret += len(A1) - i1
      else:
        A[i] = A1[i1]
        i1 += 1

  return ret

def merge_sort(a):
  n = len(a)
  if n == 1:
    return 0

  a1 = a[:n/2]
  a2 = a[n/2:]

  ret1 = merge_sort(a1)
  ret2 = merge_sort(a2)
  # merge not merge_sort
  ret = ret1+ret2+merge(a1, a2, a)  
  return ret
\end{python}

\subsection{Binary Index Tree \& Inversion Count}
Given $A$, calculate each element's inversion number. 

Construct a BIT (\ref{BIT}) with length $max(A)+1$. Let BIT maintains the index of values. Scan the element from left to right (or right to left depends on the definition of inversion number), and set the index equal val to 1. Use the prefix sum to get the inversion number.

\pyinline{get(end) - get(a)} get the count of number that appears \textit{before} $a$ (i.e. already in the BIT) and also \textit{larger} than $a$. 

Possible to extend to handle duplicate number. 
\\
Core clues:
\begin{enumerate}
\item BIT maintains \textbf{index of values} to count the number of at each value.
\item \pyinline{get(end) - get(a)} to get the inversion count of $a$.
\end{enumerate}
\begin{python}
def inversion(self, A):
    bit = BIT(max(A)+1)
    ret = []
    for a in A:
        bit.set(a, 1)  # += 1 if possible duplicate 
        inversion = bit.get(max(A)+1) - bit.get(a)
        ret.append(inversion)

    return ret
\end{python}

\subsection{Segment Tree \& Inversion Count}\label{segmentTreeInversionCount}
Compared to BIT, Segment Tree can process queries of both $idx \rightarrow sum$ and $sum \rightarrow idx$; while BIT can only process $idx \rightarrow sum$.

Core clues:
\begin{enumerate}
\item Segment Tree maintains \textbf{index of values} to count the number of at each value.
\item \pyinline{get(root, end) - get(root, a)} to get the inversion count of $a$.
\end{enumerate}
\begin{python}
class SegmentTree:
  def __init__(self):
    self.root = None

  def build(self, root, lo, hi):
    if lo >= hi: return
    if not root: root = Node(lo, hi)

    root.left = self.build(root.left, lo, (lo+hi)/2)
    if root.left: 
      root.right = self.build(root.right, (lo+hi)/2, hi)

    return root

  def set(self, root, i, val):
    if root.lo == i and root.hi-1 == root.lo:
      root.cnt_this += val
    elif i < (root.lo+root.hi)/2:
      root.cnt_left += val
      self.set(root.left, i, val)
    else:
      self.set(root.right, i, val)

  def get(self, root, i):
    if root.lo == i and root.hi-1 == root.lo:
      return root.cnt_left
    elif i < (root.lo+root.hi)/2:
      return self.get(root.left, i)
    else:
      return (
          root.cnt_left + root.cnt_this +
          self.get(root.right, i)
      )


class Solution:
  def _build_tree(self, A):
    st = SegmentTree()
    mini, maxa = min(A), max(A)
    st.root = st.build(st.root, mini, maxa+2)  
    # maxa+1 is the end dummy
    return st

  def countOfLargerElementsBeforeElement(self, A):
    st = self._build_tree(A)
    ret = []
    end = max(A)+1
    for a in A:
      ret.append(
          st.get(st.root, end) - st.get(st.root, a)
      )
      st.set(st.root, a, 1)

    return ret
\end{python}

\subsection{Reconstruct Array from Inversion Count}\label{inversionReconstruct}
Given a \textit{sorted} numbers with their associated inversion count (\# larger numbers before this element). $A[i].val$ is the value of the number, $A[i].inv$ is the inversion number. Reconstruct the original array $R$ that consists of each $A[i].val$.

Brute force can be done in $O(n^2)$. Put the $A[i].val$ into $R$ at slot s.t. the \# \textit{empty} slots before it equals to $A[i].inv$.

\rih{BST}. Possible to use BST to maintain the empty slot indexes in the original array. Each node's rank indicates the count of empty indexes in its left subtree. But need to maintain the deletion.  

\rih{Segment Tree}. Use a segment tree to maintain the size of empty slots. Each node has a $start$ and a $end$ s.t slot indexes $\in [start, end)$. Go down to find the target slot, go up to decrement the size of empty slots. 

Caveat: need to sort the array in the preprocessing step. 

Reconstruction of array cannot use BIT since there is no map of $prefixSum \rightarrow i$.

\begin{python}
class Node:
  def __init__(self, lo, hi, cnt):
    self.lo = lo
    self.hi = hi
    self.cnt = cnt  # size of empty slots

    self.left = None
    self.right = None

  def __repr__(self):
    return repr("[%d,%d)" % (self.lo, self.hi))


class SegmentTree:
  """empty space"""
  def __init__(self):
    self.root = None

  def build(self, lo, hi):
    """a node can have right ONLY IF has left"""
    if lo >= hi: return
    if lo == hi-1: return Node(lo, hi, 1)

    root = Node(lo, hi, hi-lo)
    root.left = self.build(lo, (hi+lo)/2)
    root.right = self.build((lo+hi)/2, hi)
    return root

  def find_delete(self, root, sz):
    """
    :return: index
    """
    root.cnt -= 1
    if not root.left:
      return root.lo
    elif root.left.cnt >= sz:
      return self.find_delete(root.left, sz)
    else:
      return self.find_delete(root.right,
                  sz - root.left.cnt)


class Solution:
  def reconstruct(self, A):
    st = SegmentTree()
    n = len(A)
    st.root = st.build(0, n)
    A = sorted(A, key=lambda x: x[0])
    ret = [0]*n
    for a in A:
      idx = st.find_delete(st.root, a[1]+1)
      ret[idx] = a[0]

    return ret


if __name__ == "__main__":
  # (val, inv)
  A = [(5, 0), (2, 1), (3, 1), (4, 1,), (1, 4)]
  assert Solution().reconstruct(A) == [5, 2, 3, 4, 1]
\end{python}

\runinhead{Duplicate.} What if the array contains duplicate elements? Use a \pyinline{Counter} to count the duplicate items already in the result.