Der Rang eines Elements $x$ in einem Array $A$ ist die Anzahl der Elemente $z \in A$ mit $z \leq x$. Wie finde ich in einem Array das \(k\)-kleinste Element, also das von Rang $k$? Ich kann natürlich das Array sortieren und dann array[k] zurückgeben:

def quickSelect(array, k):
    return quicksort(array)[k]

Das klingt aber verschwenderisch. Anstatt Quicksort direkt aufzurufen, verwenden wir die Idee von Quicksort, tätigen aber nur die rekursiven Aufrufe, die wir tatsächlich benötigen. Wenn z.B. 80 Elemente kleiner sind als das Pivot und wir das Element vom Rang $k=60$ suchen, dann können wir das Array right der größeren Elemente getrost links liegen lassen (bzw. rechts liegen lassen). Der Code sieht dann so aus:

def quickselect(array,k):
	n = len(array)
	if (n <= 1):
		return array[0]
	pivot = array[randint(0,n-1)]	
	left = [x for x in array if x < pivot]
	same = [x for x in array if x == pivot]
	right= [x for x in array if x > pivot]

	if (k < len(left)):		
		return quickselect(left,k)
	elif (k >= len(left) + len(same)):		
		return quickselect(right, k - len(left) - len(same))
	else:		
		return pivot

Wir hatten ja schon angesprochen, dass es auf das gleiche herauskommt, wenn wir in jedem Schritt das Pivot zufällig wählen, anstatt das Array am Anfang zufällig zu mischen. Am Besten verstehen wir Quickselect als ein nur teilweise ausgeführtes Quicksort. Betrachten wir zum Beispiel das Array [in, of, it, as ,is, be, to] und $k=4$ und die Folge rekursiver Aufrufe von quickselect:

quickselect([in, of, it, as, is, be, to], 5) 
quickselect([of, it, is, to], 2)
quickselect([it, is], 2)
it

und betrachten nochmal den Quicksort-Baum dieses Arrays:

Kreisen wir den Teil des Baumes aus, der tatsächlich von quickselect abgearbeitet wird:

Für Quicksort hatten wir die Indikatorvariable $I_{x,y}$ definiert:

\begin{align*} I_{x,y} & = \begin{cases} 1 & \textnormal{wenn $x$ ein echter Vorfahre von $y$ im Quicksortbaum ist,} \\ 0 & \textnormal{ sonst.} \end{cases} \end{align*}

Wir haben auch gesehen, dass $I_{x,y}=1$ genau dann ist, wenn Quicksort $x$ mit $y$ vergleicht und $x$ dabei Pivot ist. Bei Quickselect kommt noch eine weitere Bedingung hinzu: der Vergleich wird nur dann ausgeführt, wenn $x$ auch Vorfahre (echt oder nicht echt) des Elements $r$ von Rank $k$ ist. Definieren wir also

\begin{align*} J_{x,y} & = \begin{cases} 1 & \textnormal{ wenn $x$ Vorfahre von $r_k$ und echter Vorfahre von $y$ ist, }\\ 0 & \textnormal{ sonst.} \end{cases} \end{align*}

Sei $S_{x,y}$ die Menge

\begin{align*} S_{x,y} := \{z \in \textnormal{Array} \ | \ \min(x,y,r_k) \leq z \leq \max(x,y,r_k)\} \ , \end{align*}

wobei $r_k$ das gesuchte Element vom Rang $k$ ist. Wie bei Quicksort sehen wir, dass $J_{x,y}=1$ genau dann gilt, wenn $x$ von allen Elementen in $S_{x,y}$ im Array am weitesten links steht. In einem zufällig sortierten Array geschieht das mit Wahrscheinlichkeit

\begin{align*} \Pr[J_{x,y}=1] & = \frac{1}{|S_{x,y}|+1} \end{align*}

Wenn wir nun, um die Notation zu vereinfachen, annehmen, dass unser Array die Elemente $1,\dots,n$ in zufälliger Reihenfolge enthält, dass ist dies

\begin{align} \Pr[J_{x,y}=1] & = \frac{1}{ \max(x,y,k) - \min(x,y,k)+1} \ . \label{max-min} \end{align}

Um diesen Ausdruck zu verstehen, betrachten wir wieder die $\Pr[J_{x,y}=1]$ für alle Werte von $x$ und $y$ als Matrix.

Wobei wir die Matrix in sechs Bereiche aufteilen, je nachdem, in welcher Reihenfolge $x$, $y$ und $k$ stehen. Da wir nur $x \lt y$ betrachten (und später mit 2 multiplizieren), zeigen wir nur drei dieser Bereiche. Es gilt nun für $x \lt y$:

\begin{align*} \Pr[J_{x,y}=1] & = \begin{cases} \frac{1}{k-x+1} & \textnormal{im Bereich 1} \\ \frac{1}{y-x+1} & \textnormal{im Bereich 2} \\ \frac{1}{y-k+1} & \textnormal{im Bereich 3} \end{cases} \end{align*}

und somit gilt

\begin{align*} \E[\textnormal{Anzahl der Vergleiche}] & = \sum_{x \ne y} \Pr[J_{x,y}=1] \\ & = \sum_{x \ne y} \frac{1}{\max(x,y,k) - \min(x,y,k)+1}\\ & = 2 \cdot \left( \underbrace{\sum_{1 \leq x \lt y \lt k}\frac{1}{k-x+1}}_{\textnormal{Bereich 1}} + \underbrace{\sum_{\substack{1 \leq x \leq k \leq y \leq n\\x \ne y}} \frac{1}{y-x+1}}_{\textnormal{Bereich 2}} \\ + \underbrace{\sum_{k \lt x \lt y \leq n} \frac{1}{y-k+1}}_{\textnormal{Bereich 3}} \right) \end{align*}

Gehen wir jeden Bereich separat an.

\begin{align*} \textnormal{Bereich 1} & = \sum_{1 \leq x \lt y \lt k}\frac{1}{k-x+1} \\ & = \sum_{1 \leq x \lt k}\frac{1}{k-x+1} \sum_{x \lt y \lt k} 1 \\ & = \sum_{1 \leq x \lt k}\frac{1}{k-x+1} (k-x-1) \\ & \leq \sum_{1 \leq x \lt k} 1 = k \ .\\ \textnormal{Bereich 3} & = \sum_{k \leq x \lt y \leq n} \frac{1}{y-k+1} \\ & = \sum_{k \lt y \leq n} \frac{1}{y-k+1} \sum_{k \leq x \lt y} 1 \\ & = \sum_{k \lt y \leq n} \frac{1}{y-k+1} (y-k) \\ & \leq \sum_{k \lt y \leq n} 1 = n-k\ . \end{align*}

Bereich 1 und 3 ergeben also zusammen $n$. Bereich 2 ist am schwierigsten abzuschätzen. Zoomen wir mal rein in die Matrix:

Wir sehen, dass jede fallende Diagonale $i$ mal den Bruch $\frac{1}{i}$ enthält und somit $1$ zur Summe beiträgt, für $i=2,\dots, n$. Naja, für $i \gt \min(k, n-k+1)$ sind die Diagonalen nicht mehr "voll". Aber für eine Abschätzung nach oben tun wir so, als wären sie es. Wir haben also $n-1$ Diagonalen die jeweils höchstens 1 ergeben. Somit trägt Bereich 2 höchstens $n$ bei. Wenn Sie es formaler haben wollen:

\begin{align*} \textnormal{Bereich 2} & = \sum_{\substack{1 \leq x \leq k \leq y \leq n\\x \ne y}} \frac{1}{y-x+1} \leq \sum_{1 \leq x \leq k \leq y \leq n} \frac{1}{y-x+1} \\ & = \sum_{d=1}^{n} \frac{1}{d} \cdot \left|\{(x,y) \in [n] \times [n] \ | \ x \leq k \leq y \textnormal{ und } y-x+1=d \}\right| \tag{$d$-te Diagonale betrachten} \\ & \leq \sum_{d=1}^{n} \frac{1}{d} \cdot \left|\{(x,y) \in \Z \times \Z \ | \ x \leq k \leq y \textnormal{ und } y-x+1=d \}\right| \tag{Diagonale voll machen}\\ & = \sum_{d=1}^{n} \frac{1}{d} \cdot \left|\{x \in \Z \ | \ x \leq k \leq x + d - 1 \}\right| \tag{weil $y=x+d-1$ gilt} \\ & = \sum_{d=1}^{n} \frac{1}{d} \cdot d = n \end{align*}

Die drei Bereiche ergeben sommit höchstens $2n$. Soweit die obere Hälfte der Matrix, also der Fall $x \lt y$. Der untere Teil trägt nochmal höchstens $2n$ bei.