Quick sort

Il quick sort fa parte degli algoritmi di sorting. $\in \Theta (n\log n)$

Input Sequenza di $n$ valori $A=<a_0,a_1,...,a_{n-1}>$.

Output Permutazione $<a_0^{\prime },a_1^{\prime },...,a_{n-1}^{\prime }>$ della sequenza $A$ tale che $a_0^{\prime }\le a_1^{\prime }\le ...\le a_{n-1}^{\prime }$

title: Attenzione
Come costo computazionale calcoliamo i confronti eseguiti tra i valori di A.

Anche questa volta, come per il merge sort, si utilizza la tecnica dividi et impera.

1. Divide: scegliere un indice random t, mettere a destra tutti gli elementi > A[t], e a sinistra tutti quelli < A[t]. A questo punto si avrà un indice q, ovvero la posizione giusta per A[t] (quando l’array è composto da un solo elemento è già ordinato, quindi caso base)
2. Impera: ordina A[0..q-1] e A[q+1..n-1] ricorsivamente

QuickSort(A, p, r):
	if p < r then
		q := Partition(A, p, r)
		QuickSort(A, p, q-1)
		QuickSort(A, q+1, r)

La chiamata principale è QuickSort(A, 0, n-1). Per la funzione Partition si ha

Partition(A, p, r):
	// qui si potrebbe prendere un indice random, vedi dopo
	pivot := A[r]

	i := p - 1

	// esattamente r-p confronti
	for j = p to r - 1 do
		if A[j] <= pivot then
			i := i+1
			scambia A[i], A[j]
	scambia A[r], A[i+1]
	
	return i + 1

$$T(n)=\begin{array}{c}\{\begin{array}{ll}0& \text{mbox}sen=1\\ T(1)+T(n-q-1)+n-1& \text{mbox}altrimenti\end{array}\end{array}$$

Problemino

C’è un problema ad utilizzare l’ultimo elemento come pivot, ovvero che se quella è la sua posizione, il costo computazionale sale a $\Theta (n^2)$.

Si ha una partizione sbilanciata, perché si ha che $q=n-1\Rightarrow n-q-1=0$.

$$T(n)=\begin{array}{c}\{\begin{array}{ll}0& \text{mbox}sen=1\\ T(n-1)+n-1& \text{mbox}altrimenti\end{array}\end{array}$$

Con una partizione perfettamente bilanciata (il pivot va a finire sempre a metà della partizione), invece, si può utilizzare il Master theorem, e si ha che il costo è di appena $O(n\log n).$

$$T(n)=\begin{array}{c}\{\begin{array}{ll}0& \text{mbox}sen=1\\ 2\cdot T(\frac{n}{2})+n-1& \text{mbox}altrimenti\end{array}\end{array}$$

${\log }_{2}2=1=d$

Per avvicinarci al caso di una partizione perfettamente bilanciata, si può prendere il pivot a caso, anziché sempre l’ultimo dell’array. Così facendo il numero atteso di confronti di A è $\Theta (n\log n)$.

asd_14