Informatica 2 Liceo Scientifico Scienze Applicate/BubbleSort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
Nessun oggetto della modifica |
|||
Riga 1:
{{Informatica 2 Liceo Scientifico Scienze Applicate}}
== Ordinare un vettore: l'algoritmo del BubbleSort ==
Per ordinare gli elementi di un vettore dal piu' piccolo al piu' grande si possono usare diversi algoritmi, quello piu' semplice da spiegare e' il BubbleSort e quello piu' veloce e' il QuickSort. Un algoritmo e' un particolare programma che risolve una classe di problemi (nel nostro caso l'ordinamento degli elementi di un vettore) con una certa efficienza ( generalmente espressa in termini di velocita' di calcolo).
== Bubblesort ==
Per ordinare un vettore di n elementi bisogna fare n-1 passate, ad ogni passata l'elemento piu' piccolo rimasto nella parte di vettore ancora da ordinare viene spostato nella posizione corretta, per ordinare il vettore bastano n-1 passate perche' sistemati i primi n-1 elementi anche l'ultimo numero e' per forza di cose al posto giusto. In una singola passata , pensiamo sia la passata i-esima si prendono in considerazione tutti gli elementi partendo dall'ultimo (indice n-1) fino a quello con l'indice con lo stesso numero della passata, ogni elemento considerato ad esempio quello k-esimo viene confrontato con quello che lo precede k-1-esimo e se vett[k] < vett[k-1] i due elementi del vettore si scambiano fra loro , altrimenti si passa a considerare l'elemento successivo. Facciamo un esempio , vettore di 6 elementi , passate da fare 5, nella prima passata si ha
[[File:Bubblesort1.png|Bubblesort 1^ passata]]
come si vede, alla fine della prima passata il vettore e' composto da due parti una ordinata (colore verde) che contiene il numero piu' piccolo (2) e una che deve essere ancora ordinata, la seconda passata si occupa di ordinare soltanto di quest'ultima, si vede che per fare la prima passata bisogna considerare via via gli elementi in giallo con il corrispondente elemento che lo precede, sono queste coppie di valori che vengono confrontate ed eventualmente scambiate fra loro
[[File:Bubblesort2.png|Bubblesort 2^ passata]]▼
nella seconda passata: <br />
[[File:Bubblesort3.png|Bubblesort 3^ passata]]▼
[[File:Bubblesort4.png|Bubblesort 4^ passata]]▼
[[File:
il vettore ordinato e' composto ora da due numeri e il vettore da ordinare e' diventato piu' piccolo, si nota che il numero di confronti che si devono fare si riduce di conseguenza di una unità ad ogni passata.Vediamo la passata 3<br />
Vediamo la passata 4<br />
vediamo la passata 5<br />
si nota che durante la passata 4 non ci sono stati scambi , quando non ci sono scambi durante tutta una passata il vettore risulta ordinato e ele passate successive non sono piu' necessarie, in questa spiegazione e nel programma seguente non utilizzeremo questa particolarita' che consente di velocizzare la fine dell'algoritmo.<br />
Il programma e' caratterizzato da un primo ciclo for che conta le passate ( conta da 1 ) e all'interno della singola passata c'e un secondo for che prende in analisi i diversi elementi J (partendo dal fondo n-1 fino a quello di indice pari al numero della passata) che devono essere confrontati con l'elemento del vettore che lo precede J-1 , si nota poi la necessita' dell'uso della variabile temp per poter scambiare due celle di un vettore senza perdersi uno dei valori delle celle.<br />
In questo programma l'ordinamento e' fatto su un vettore di stringhe (parole), in questo caso l'ordinamento e' quello alfabetico (antonella minore di zorro)
=== BubbleSort ===
<source lang="c">
#include <cstdlib>
#include <iostream>
#include <string>
using namespace std;
/* dato un vettore disordinato ordinarlo con il bubblesort
e poi stamparlo
*/
int main(int argc, char *argv[])
{{Avanzamento|25%|4 dicembre 2014}}▼
{
int n=5;
string vett[5];
int i,j;
string temp;
for (i=0;i<n;i++)
{ cout<<"inserisci il "<<i<<" elemento ";
cin>>vett[i];
}
cout<<"stampa vettore disordinato"<<endl;
for (i=0;i<n;i++)
{ cout<<vett[i]<<" , ";
}
cout<<endl;
for (i=1;i<n;i++)
for ( j= n-1;j>=i;j--)
if(vett[j]<vett[j-1])
{ temp= vett[j];
vett[j]=vett[j-1];
vett[j-1]=temp;
}
cout<<"stampa vettore ordinato"<<endl;
for (i=0;i<n;i++)
{ cout<<vett[i]<<" , ";
}
cout<<endl;
system("PAUSE");
return 0;
}
</source>
[[Categoria:Informatica 2 Liceo Scientifico Scienze Applicate|BubbleSort]]
| |||