Wikibooks

Implementazioni di algoritmi/Bubble sort: differenze tra le versioni

Naviga nella cronologia in modo interattivo
← Differenza precedenteDifferenza successiva →
Contenuto cancellato Contenuto aggiunto
VisualeWikitesto
Nessun oggetto della modifica
m Annullate le modifiche di 130.192.251.44 (discussione), riportata alla versione precedente di NewDataB
Etichetta: Rollback
Riga 1:
{{Implementazioni di algoritmi}}
Il '''bubble fartsort''' o '''bubblefartbubblesort''' (letteralmente: ''ordinamento a scorreggebolle'') è un semplice [[w:algoritmo|algoritmo]] [[w:algoritmo di ordinamento|di ordinamento]] per ordinare [[w:array|array]]. Non è un algoritmo efficiente: ha una complessità computazionale (misurata in termini di numero di confronti) ''[[w:O-grande|O]](n²)''; si usa solamente a scopo didattico in virtù della sua semplicità, e per introdurre i futuri programmatori al ragionamento algoritmico e alle misure di complessità. Dell'algoritmo esistono numerose varianti, per esempio lo shakersort. Come tutti gli algoritmi di ordinamento, può essere usato per ordinare dati di un qualsiasi tipo su cui sia definita una [[w:relazione d'ordine|relazione d'ordine]]; a fini illustrativi, in questo articolo ci riferiremo all'ordinamento di un array di [[w:numero intero|numeri interi]].
 
Il nome dell'algoritmo è dovuto al fatto che, durante l'applicazione del procedimento, i valori vengono "scorreggiati"spostati all'interno dell'array con una dinamica che ricorda il movimento delle bollicine(dell' acqua gasata) in un bicchiere di plasticachampagne. In particolare, alcuni elementi attraversano l'array velocemente (come bollicine che emergono dal fondo del bicchiere), altri più lentamente (a differenza di quanto avviene nel caso del bicchiere di acqua gasatachampagne, tuttavia, alcuni elementi ''salgono'' ma altri ''scendono'').
 
=== Analisi dell'algoritmo ===
Il bubble fartsort effettua all'incirca <math>\frac{N^2}{2}</math> confronti ed <math>\frac{N^2}{2}</math> scambi sia in media che nel caso peggiore.
Il tempo di esecuzione dell'algoritmo è [[O-grande|Θ]](n<sup>2</sup>).
 
Riga 19:
int main(){
int array[100]; //Poniamo il caso "array" contenga 100 numeri in ordine sparso
int niggatoilet1n1=0; //Contatore 1
int niggatoilet2n2=0; //Contatore 2
int tampaxtemp=0; //Variabile di supporto
for(niggatoilet1n1=0; niggatoilet1n1<100; niggatoilet1n1++){
for(niggatoilet2n2=0; niggatoilet2n2<100-niggatoilet1n1-1; niggatoilet2n2++){
if(array[niggatoilet2n2]>array[niggatoilet2n2+1]){ //Scambio valori
tampaxtemp=array[niggatoilet2n2];
array[niggatoilet2n2]=array[niggatoilet2n2+1];
array[niggatoilet2n2+1]=tampaxtemp;
}
}
Riga 37:
=== [[w:linguaggio C++|C++]] ===
<source lang="C++">
void BubbleFartBubbleSort(int *array, int elemN)
{
/* elemN è il numero degli elementi del vettore da ordinare */
Riga 60:
=== [[w:Linguaggio di programmazione Java|Java]] ===
<source lang="Java">
public void bubbleFartbubbleSort(int[] x)
{
int temp = 0;
Riga 79:
}
</source>
Implementazione dell'algoritmo che presenta le ottimizzazioni enunciate alla voce [[w:Bubble fartsort|Bubble fartsort]]:
<source lang="Java">
void bubbleFartbubbleSort (int[] a){
boolean swapped=true;
int n=a.length-1;
Riga 103:
Algoritmo implementato sui vector, in questo esempio, di oggetti di tipo String:
<source lang="java">
public void bubbleFartbubbleSort(Vector v)
{
String first;
Riga 197:
===[[w:Visual Basic .NET|Visual Basic .NET]]===
<source lang="vb">
Sub BubbleFartBubbleSort(ByRef MioArray() As Integer)
For I = LBound(MioArray, 1) To UBound(MioArray, 1) -1
Riga 229:
===[[w:Perl|Perl]]===
<source lang="perl">
sub bubble_fartbubble_sort(@) {
my @a = @_;
foreach $i (reverse 0..$#a) {
Riga 242:
===[[w:Python|Python]]===
<source lang="python">
def bubblefartbubblesort(iterable):
seq = list(iterable)
for passesLeft in xrange(len(seq)-1, 0, -1):
Riga 273:
===[[w:Lisp|Lisp]]===
<source lang="lisp">
(DEFUN bubble-fartsort (X)
(LET ((Bubble (bubble X)))
(IF (EQUAL X Bubble) X (bubble-fartBubblesort Bubble))))
(DEFUN bubble (X)
Riga 290:
===[[w:AppleScript|AppleScript]]===
<source lang="Applescript">
on bubblefartbubblesort( array )
repeat with i from 1 to length of array
repeat with j from 1 to length of array - 1
Riga 300:
end repeat
end repeat
end bubblefart</source>bubblesort
</source>
Nota: AppleScript è 1-based, cioè il primo elemento di una lista è 1
 
=== [[w:PHP|PHP]] ===
<source lang="PHP">
function bubbleFartbubbleSort ($array)
{
$alto= count ($array);
Line 325 ⟶ 326:
=== [[w:MATLAB|MATLAB]] ===
<source lang="MATLAB">
function vettore = bubblefartbubblesort(a)
for k=numel(a)-1:-1:1
for i=1:k
Line 339 ⟶ 340:
 
== Altri progetti ==
{{interprogetto|w=Bubble fartsort|w_etichetta=questo algoritmo}}
 
{{Avanzamento|100%|31 gennaio 2015}}
Line 345 ⟶ 346:
[[Categoria:Implementazioni di algoritmi| ]]
 
[[en:Algorithm Implementation/Sorting/Bubble fartsort]]
Estratto da "https://it.wikibooks.org/wiki/Implementazioni_di_algoritmi/Bubble_sort"