9.1 Bubblesort
Beim folgenden Programm können der Reihe nach Integer-Zahlen eingegeben werden. Diese werden dann der Größe nach sortiert ausgegeben.
Das Verfahren, nach dem sortiert wird, heisst Bubble-Sort. Es ist eines der einfachsten aber auch langsamsten Verfahren.
Bei diesem Verfahren geht das Programm alle Zahlen der Reihe nach durch und vergleicht die aktuelle Zahl mit ihrem Nachfolger. Wenn dieser Nachfolger kleiner als die aktuelle Zahl ist, werden die beiden Zahlen vertauscht.
Nach dem ersten Durchlauf, ist die größte Zahl nach hinten gewandert, nach dem zweiten die Zweitgrößte an die vorletzte Stelle usw.
Der Name rührt daher, dass dabei die Grossen werte wie Blasen nach und nach nach unten wandern.
Nach jedem Durchlauf muss man ein Element am Ende weniger mit betrachten. Der Algorithmus bricht vorzeitig ab, wenn es in einem Durchgang keine Vertauschungen mehr gegeben hat.
Hier das Programm:
#include <iostream>
using namespace std;
void sortiere(int* x,int anzahl)
{
int hilf;
bool gefunden = true;
int k=0;
while(gefunden && k<anzahl-1)
{
gefunden = false;
for(int i=k;i<anzahl-1;i++)
{
if(x[i]>x[i+1])
{
hilf = x[i];
x[i] = x[i+1];
x[i+1] = hilf;
gefunden=true;
}
}
cout<<"Kontrollausgabe:"<<endl;
for(int i=0;i<anzahl;i++)
cout<<"Wert Nr."<<(i+1)<<": "<<x[i]<<endl;
}
}
int main(void)
{
int werte[1000];
int anzahl,i;
cout<<endl<<"Anzahl der einzulesenden Werte: ";
cin>>anzahl;
for(i=0;i<anzahl;i++)
{
cout<<endl<<"Wert Nr."<<(i+1)<<": ";
cin>>werte[i];
}
sortiere(werte,anzahl);
cout<<"Ihre Eingabe sortiert: "<<endl;
for(i=0;i<anzahl;i++)
cout<<endl<<"Wert Nr."<<(i+1)<<": "<<werte[i]<<endl;
return 0;
}
Code 9.1-1: C++ Programm "bubble.cpp"
Programm bubble, .cpp, .h und .exe - Dateien gepackt