2.07 Lezione 7

Shellsort

Shellsort ci permette di considerare elementi dell'array che non sono sequenziali. L'idea è quella di muovere gli elementi più di una posizione alla volta andando a fare un h-sorting dell'array.

Se ad esempio prendiamo h=3 confronteremo ogni elemento con l'elemento 3 posizioni dopo all'elemento corrente.

Se prendiamo, ad esempio, h=3, dopo la prima iterazione mi troverò con tante sequenze di 3 elementi che sono parzialmente ordinate. Alla prossima iterazione, diminuirò h di 1, ed avrò quindi h=2, fino ad arrivare ad h=1.

Questo ci permette di fare gradualmente sempre meno scambi.

public class Shell{
  public static void sort(Comparable[] a){
    int N = a.length;
    
    int h = 1;	//step
    while(h < N/3) 
      h = 3*h +1;	// 1, 4, 13, 40, 121 ...
    
    while(h >= 1){
      // h-sort l'array
      for(int i = h; i < N; i++){
        for(int j = i; j >= h && less(a[j], a[j-h]); j-=h)
          exch(a, j, j-h);
      }
      h = h/3;
    }
  }
}

Diverse sequenze

Quale incremento utilizzare?

• Non usare potenze di due
• Si potrebbero usare le potenze di due meno uno
• La computazione è semplice utilizzando 3x + 1 Nel codice viene infatti utilizzato 3*h +1

Parliamoci chiaro...

L'algoritmo essenzialmente funziona in questo modo:

abbiamo un array di n elementi (12). Calcoliamo h = n/2 (6); questo indice h ci serve per poter comparare due elementi che sono h posizioni di distanza.

Continuiamo in questo modo per tutti gli elementi fino all'ultimo elemento dell'indice superiore (quindi fino all'iterazione i = h = n/2 = 12/2 = 6).

Durante il controllo, se il secondo elemento è minore del primo, si effettua uno scambio e si continua.

Finita la prima iterzione, h diventa h = h/2 (3) e procediamo allo stesso modo, ma controlliamo anche le posizioni precedenti:

esempio:

abbiamo l'array 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 con h= 3.

stiamo controllando la coppia 4-1, visto che 1<4 scambiamo ed otteniamo: 10, 9, 8, 7, 6, 5, 1, 3, 2, 4 .

a questo punto non ci fermiamo ma controlliamo anche la coppia 1-7, visto che 1<7 scambiamo ed otteniamo: 10, 9, 8, 1, 6, 5, 7, 3, 2, 4 . A questo punto ci fermiamo e iniziamo una nuova iterazione.

algoritmo	migliore	Media	Peggiore
selection sort	N2	N2	N2
insertion sort	N	N2	N2
Shellsort(3x+1)	N log N	?	N3/2

Shuffling

L'obbiettivo è riordinare un arrai in modo tale che esso risulti uniforme. Questo si ottiene permettendo che tutti gli scambi abbiano pari probabilità. Per fare lo shuffling in maniera corretta bisogna consentire a tutte le permutazioni di essere equiprobabili.

Soluzioni

Un metodo molto semplice sarebbe quello di assegnare ad ogni elemento dell'array un numero reale random, e poi andare ad ordinare l'array.

Il problema è che il sorting ci richiede un tempo, nel caso migliore, linearitmico. Noi, invece, vogliamo effettuare lo shuffling in un tempo lineare.

Esempi

Microsoft fu incaricata, in un accordo con la commissione europea, a creare un sito dove gli utenti potessero scegliere il browser di default in windows 7. L'accordo diceva che i browser da scaricare dovevano comparire in ordine random ogni volta che ci si collegava al sito, in modo da non presentare una preferenza per i browser.

Nell'algoritmo presentato da microsoft, il 50% delle volte internet explorer appariva nell'ultima posizione. Ovviamente, lo shuffling non era uniforme.

Soluzione di Microsoft

public int compareTo(Browser that){
  double r = Math.random();
  if(r < 0.5) return -1;
  if(r > 0.5) return +1;
  return 0
}

Knuth shuffle (tempo lineare)

Possiamo usare la variante degli algoritmi visti in precedenza nella lezione 6 (insertion sort). Ad ogni passo i andiamo a calcolare un numero intero random, tra 0 ed i, e facciamo lo scambio tra le posizioni i ed r.

Possiamo vedere una Demo dell'algoritmo.

Importante: Se invece di calcolare r, in maniera random, tra 0 e i-1 invece che tra 0 e i, non avremmo un algoritmo equiprobabile, perchè per ogni iterazione non viene contemplato lo scambio tra la posizione attuale e la posizione attuale, quindi l'elemento i non potrà avere la possibilita (randomica) di rimanere nello stesso posto.

Infatti, se guardiamo l'ultimo elemento, esso non potrà mai occupare l'ultima posizione dell'array shuffled, proprio perchè la sua nuova posizione viene calcolata tra 0 e i-1.

Implementazione

public class StdRandom{
  ...
  public static void shuffle(Object[] a){
    int N = a.length;
    for(int i = 0; i < N; i++){
      int r = StdRandom.uniform(i + 1);
      exch(a, i, r);
    }
  }
}