SelectSort

Questa lezione ha come oggetto l'algoritmo di ordinamento SelectSort.

Sia S una sequenza di n numeri distinti. Dato 1 <= i <= n e un elemento x di S, diremo che x è l'elemento di ordine i di S se esistono i-1 elementi in S più piccoli di x. In particolare, l'elemento di ordine 1 è detto minimo di S, l'elemento di ordine n è detto massimo di S, e l'elemento di ordine (n+1) div 2 (divisione intera) è detto mediana di S. Il problema della selezione è il seguente: dati in ingresso una sequenza S di n numeri distinti e un indice 1 <= i <= n, fornire in uscita l'elemento di ordine i di S.

Un algoritmo che risolve il problema della selezione con complessità lineare è il seguente:

1. Dividi gli n elementi di S in n div 5 gruppi di 5 elementi ciascuno e un eventuale gruppo di n mod 5 elementi;
2. trova la mediana di ogni singolo gruppo ordinando gli elementi di ciascun gruppi usando MergeSort;
3. usa Select ricorsivamente per trovare la mediana x delle mediane dei singoli gruppi;
4. partiziona la sequenza S attorno alla mediana delle mediane x usando la procedura Partition. Sia k la posizione di x dopo la partizione;
5. se i = k, allora restituisci x. Altrimenti, usa Select ricorsivamente per trovare l'elemento di ordine i sulla metà di sinistra della partizione, qualora i < k, oppure per trovare l'elemento di ordine i-k sulla metà destra della partizione, qualora i > k.

Select(A,p,r,i)
// Uso un vettore B[1, ... , (length(A) div 5) + 1]
// p <= r, 1 <= i <= r-p+1
// Inizio Parte I
IF (p = r)
 return A[p]
ENDIF
n = r-p+1
FOR (j = 1 to n div 5)
   MergeSort(A, p+5*(j-1), p+5*j-1)
ENDFOR
IF ((n mod 5) != 0)
 MergeSort(A, p+5*j, r)
ENDIF
// Inizio Parte II
FOR (j = 1 to n div 5)
     B[j] = A[p + (j-1)*5 + 2]
ENDFOR
IF ((n mod 5) != 0)
 q = p+5*j
 B[j+1] = A[q +  (r-q) div 2 ]
ENDIF
// Inizio Parte III
m = (n div 5) + 1
x = Select(B,1,m, (m+1) div 2 )
// Inizio Parte IV
j = ArraySearch(A,p,r,x)
Exchange(A,j,r)
k = Partition(A,p,r)
// Inizio Parte V
IF (i = k)
 return x
ELSE
  IF (i < k)
   Select(A,p,k-1,i)
  ELSE
   Select(A,k+1,r,i-k)
  ENDIF
ENDIF

Il metodo di ordinamento SelectSort consiste nella seguente variante dell'algoritmo QuickSort:

SelectSort(A,p,r)
IF (p < r)
  n = r-p+1 
  x = Select(A, p, r, (n+1) div 2)
  i = IndexOf(A,p,r,x)
  Exchange(A, i, r)
  q = Partition(A, p, r)
  SelectSort(A, p, q-1)
  SelectSort(A, q+1, r)
ENDIF

dove il metodo Select(A,p,r,i) trova l'elemento di ordine i cercando in A[p...r] e il metodo IndexOf(A,p,r,x) restituisce l'indice dell'elemento x cercando in A[p...r].

Scrivere una classe SelectSort che ordina, in senso crescente, un vettore casuale di interi usando il metodo SelectSort. Aggiornare la classe SortWorkBench con l'algoritmo SelectSort.