Wikibooks

Implementazioni di algoritmi/Shaker sort: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
RamaccoloBot (discussione | contributi)
5 079 modifiche
m Bot: Modifico Categoria:Algoritmi
Nessun oggetto della modifica
Riga 1:
{{Implementazioni di algoritmi}}
 
In [[w:informatica|informatica]] lo '''Shaker sort''', noto anche come '''Bubble Sort Bidirezionalebidirezionale''', '''Cocktail Sortsort''', '''Cocktail Shaker Sortsort''' o '''Shuttle Sortsort''' è un [[w:algoritmo|algoritmo]] [[w:algoritmo di ordinamento|di ordinamento]] particolarmente indicato per l'ordinamento di [[w:array|array]], è stato sviluppato dalla [[w:Sun Microsystems|Sun Microsystems]].
 
Lo shakerShaker sort è sostanzialmente una variante del [[w:bubbleBubble sort|bubbleBubble sort]] in cui l'indice del ciclo più interno, anziché scorrere continuamente dall'inizio alla fine, si cambia direzione ad ogni ciclo. Pur mantenendo la stessa [[w:complessità|complessità]], ovvero ''O(n²)'', lo shakersortShaker sort riduce la probabilità che l'ordinamento abbia un costo corrispondente al [[analisi del caso peggiore|caso peggiore]].
 
Il nome shaker sortdell'algoritmo (ordinamento "a shaker", con riferimento allo strumento per preparare i [[w:cocktail|cocktail]]) suggerisce abbastanza chiaramente in cosa lo shakerShaker sort modifichi il bubbleBubble sort. Anziché scandire l'array sempre nello stesso verso (privilegiando quindi gli spostamenti di valori in quel verso), lo shakersortShaker sort semplicemente ''alterna'' una scansione in avanti e una all'indietro.
 
Tutte le ottimizzazioni e le varianti previste per il bubblesortBubble sort sono applicabiliimplementabili, con i dovuti adattamenti, anche allo shakersortShaker sort.
 
== Implementazioni ==
Riga 58:
</source>
 
Implementazione, sempre in Java, di una variante ottimizzata dello Shaker sort basata sulle ottimizzazioni previste per il [[w:Bubble sort|Bubble sort]]:
<source lang="java">
void shakerSort(int[] a){
boolean swapped=true;
int n=a.length-1;
int infLimit=0;
int supLimit=0;
int temp=0;
int j=0;
while (j<n && swapped){
swapped=false;
for (int i=j;i<n;i++){
if (a[i]>a[i+1]){
temp=a[i];
a[i]=a[i+1];
a[i+1]=temp;
swapped=true;
supLimit=i;
}
}
if (swapped){
swapped=false;
n=supLimit;
for (int i=n;i>j;i--){
if (a[i]<a[i-1]){
temp=a[i];
a[i]=a[i-1];
a[i-1]=temp;
swapped=true;
infLimit=i;
}
}
j=infLimit;
}
 
}
}
</source>
===[[w:C++|C++]]===
<source lang="Cpp">
Estratto da "https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Shaker_sort"