Shaker sort
Esecuzione dell'algoritmo
Classe	Algoritmo di ordinamento
Struttura dati	Array
Caso peggiore temporalmente	О(n²)
Ottimale	No
Manuale

In informatica lo Shaker sort, noto anche come Bubble sort bidirezionale, Cocktail sort, Cocktail shaker sort, Ripple sort, Happy hour sort o Shuttle sort è un algoritmo di ordinamento dei dati sviluppato dalla Sun Microsystems. Lo shaker sort è sostanzialmente una variante del bubble sort: si differenzia da quest'ultimo per l'indice del ciclo più interno che, anziché scorrere dall'inizio alla fine, inverte la sua direzione ad ogni ciclo. Pur mantenendo la stessa complessità, ovvero O(n²), lo shaker sort riduce la probabilità che l'ordinamento abbia un costo corrispondente al caso peggiore.

Nota: la comprensione di quanto segue richiede di avere compreso il funzionamento generale del bubble sort.

La forma più semplice dello shaker sort scorre l'intera lista ad ogni passaggio (di seguito viene riportato il caso di ordinamento discendente):

procedure shakerSort( A : lista di elementi da ordinare ) defined as:
  do
    swapped := false
    for each i in 0 to length( A ) - 2 do:
      if A[ i ] > A[ i + 1 ] then // controlla se i 2 elementi sono in ordine errato
        swap( A[ i ], A[ i + 1 ] ) // scambia di posto i 2 elementi
        swapped := true
      end if
    end for
    if swapped = false then
      // se non si eseguono scambi, si può uscire dal ciclo più esterno
      break do-while loop
    end if
    swapped := false
    for each i in length( A ) - 2 to 0 do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped // se non sono stati eseguiti scambi, allora la lista è ordinata
end procedure

Il primo passaggio verso destra spostera l'elemento più grande nella sua posizione corretta alla fine della lista, mentre il successivo passaggio verso sinistra sposterà l'elemento più piccolo nella sua posizione corretta all'inizio della lista. Il secondo passaggio completo sposterà il secondo elemento più grande ed il secondo più piccolo nelle loro posizioni corrette, e così via: dopo "i" passaggi i primi "i" elementi e gli ultimi "i" elementi della lista saranno posizionati correttamente, e non sarà necessario ricontrollarli. Il numero di operazioni può essere ridotto accorciando la parte della lista che viene ordinata ad ogni passaggio.

 procedure cocktailSort( A : lista degli elementi da ordinare ) defined as:
  // `begin` ed `end` segnano il primo e l'ultimo indice da controllare
  begin := -1
  end := length( A ) - 2
  do
    swapped := false
    // incrementa `begin` perché gli elementi prima di `begin` sono ordinati correttamente
    begin := begin + 1
    for each i in begin to end do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
    if swapped = false then
      break do-while loop
    end if
    swapped := false
    // decrementa `end` perché gli elementi dopo `end` sono ordinati correttamente
    end := end - 1
    for each i in end to begin do:
      if A[ i ] > A[ i + 1 ] then
        swap( A[ i ], A[ i + 1 ] )
        swapped := true
      end if
    end for
  while swapped
end procedure

Il bubble sort ha una asimmetria intrinseca: i valori dell'array vengono spostati velocemente in un verso (e precisamente quello in cui procede la scansione dell'array durante una iterazione) e lentamente nell'altro verso. Per esempio, se l'array viene esaminato in avanti e i numeri vengono disposti in ordine crescente, i numeri grandi si sposteranno avanti velocemente, quelli piccoli si sposteranno indietro lentamente. Possiamo chiarire meglio questo concetto con questo esempio. Si consideri questo piccolo array:

15 4 10 11 2

Durante la prima iterazione il 15 viene ripetutamente spostato (vedi bubble sort), con il seguente risultato finale:

4 10 11 2 15

Si può quindi notare che nell'arco di una sola iterazione, il "15" (numero massimo che si trovava in prima posizione) ha attraversato l'intero array. Il "2", che si trovava in una situazione simmetrica (numero minimo in ultima posizione), ha invece percorso un solo passo verso la sua collocazione definitiva.

In generale, un numero destinato alla posizione N e inizialmente collocato alla posizione M, dove N<M, richiederà M-N iterazioni per giungere alla sua cella di destinazione. Se invece M<N, il suo spostamento sarà mediamente più rapido. Il caso particolare in cui il numero destinato alla prima posizione dell'array si trovi nell'ultima corrisponde a una situazione di "caso peggiore" del bubblesort, in cui saranno necessarie tutte le N-1 iterazioni dell'algoritmo per ottenere l'array ordinato.

Il nome shaker sort (ordinamento "a shaker", con riferimento allo strumento per preparare i cocktail) suggerisce abbastanza chiaramente in cosa lo shaker sort modifichi il bubble sort. Anziché scorrere l'array sempre nello stesso verso (privilegiando quindi gli spostamenti di valori in quel verso), lo shaker sort semplicemente alterna una scansione in avanti e una all'indietro.

Tutte le ottimizzazioni e le varianti previste per il bubble sort sono applicabili, con i dovuti adattamenti, anche allo shaker sort.

• Wikibooks contiene implementazioni dello shaker sort

• (EN) Denis Howe, cocktail shaker sort, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

V · D · M Algoritmi di ordinamento
Teoria	Teoria della complessità computazionale · Notazione O Grande · Array · Lista · Stack · Coda · Ordinamento comparativo · Ordinamento adattivo
Algoritmi a scambio	Bubble sort · Shaker sort · Odd-even sort · Comb sort · Gnome sort · Quicksort
Algoritmi di selezione	Selection sort · Heap sort · Smoothsort
Algoritmi ad inserimento	Insertion sort · Shell sort · Tree sort · Library sort · Patience sorting
Algoritmi a fusione	Merge sort · Timsort
Algoritmi non comparativi	Radix sort · Bucket sort · Counting sort · Pigeonhole sort
Altri algoritmi	Rete di ordinamento · Ordinamento topologico · Ordinamento bitonico · Ordinamento delle frittelle
Algoritmi inefficienti	Stupid sort · Trippel sort

Portale Informatica: accedi alle voci di Teknopedia che trattano di informatica